Any prime number is relatively prime to any number which it does not measure. | |
Let A be a prime number, and let it not measure B.
I say that B and A are relatively prime. |
|
If B and A are not relatively prime, then some number C measures them.
Since C measures B, and A does not measure B, therefore C is not the same as A. |
|
Now, since C measures B and A, therefore it also measures A which is prime, though it is not the same as it, which is impossible. Therefore no number measures B and A.
Therefore A and B are relatively prime. | |
Therefore, any prime number is relatively prime to any number which it does not measure. | |
Q.E.D. |
Book VII Introduction - Proposition VII.28 - Proposition VII.30.