Euclid's Elements
Book VII
Proposition 29

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.

java applet or image
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.

Guide

This proposition is used in the next one and in propositions IX.12 and IX.36.


Book VII Introduction - Proposition VII.28 - Proposition VII.30.

© 1996
D.E.Joyce
Clark University