Euclid's Elements, Book VII, Proposition 31

Proposition 31

Any composite number is measured by some prime number.
Let A be a composite number. I say that A is measured by some prime number.
	Since A is composite, therefore some number B measures it.	VII.Def.13
	Now, if B is prime, then that which was proposed is done.
But if it is composite, some number measures it. Let a number C measure it.		VII.Def.11,13
Then, since C measures B, and B measures A, therefore C also measures A. And, if C is prime, then that which was proposed is done. But if it is composite, some number measures it. Thus, if the investigation is continued in this way, then some prime number will be found which measures the number before it, which also measures A. If it is not found, then an infinite sequence of numbers measures the number A, each of which is less than the other, which is impossible in numbers. Therefore some prime number will be found which measures the one before it, which also measures A. Therefore any composite number is measured by some prime number.
Therefore, any composite number is measured by some prime number.
Q.E.D.

Euclid does not explain why there can't be an infinite sequence of numbers where each number divides the previous. He simply says that is impossible. Some justification is required such as the principle Euclid uses elsewhere that any decreasing sequence of numbers is finite.

This proposition is used in the next one and in propositions IX.13 and IX.20.

Next proposition: VII.32

Previous: VII.30

Book VII introduction