VII.3

Given three numbers not prime to one another, to find their greatest common measure.

Let A, B, C be the three given numbers not prime to one another; thus it is required to find the greatest common measure of A, B, C.

For let the greatest common measure, D, of the two numbers A, B be taken; [VII.2] then D either measures, or does not measure, C.

First, let it measure it.

But it measures A, B also; therefore D measures A, B, C; therefore D is a common measure of A, B, C.

I say that it is also the greatest.

For, if D is not the greatest common measure of A, B, C, some number which is greater than D will measure the numbers A, B, C.

Let such a number measure them, and let it be E.

Since then E measures A, B, C, it will also measure A, B; therefore it will also measure the greatest common measure of A, B. [VII.2.p.1]

But the greatest common measure of A, B is D; therefore E measures D, the greater the less: which is impossible.

Therefore no number which is greater than D will measure the numbers A, B, C;

therefore D is the greatest common measure of A, B, C.

Next, let D not measure C; I say first that C, D are not prime to one another.

For, since A, B, C are not prime to one another, some number will measure them.

Now that which measures A, B, C will also measure A, B, and will measure D, the greatest common measure of A, B. [VII.2.p.1]

But it measures C also; therefore some number will measure the numbers D, C; therefore D, C are not prime to one another.

Let then their greatest common measure E be taken. [VII.2]

Then, since E measures D, and D measures A, B, therefore E also measures A, B.

But it measures C also; therefore E measures A, B, C; therefore E is a common measure of A, B, C.

I say next that it is also the greatest.

For, if E is not the greatest common measure of A, B, C, some number which is greater than E will measure the numbers A, B, C.

Let such a number measure them, and let it be F.

Now, since F measures A, B, C, it also measures A, B; therefore it will also measure the greatest common measure of A, B. [VII.2.p.1]

But the greatest common measure of A, B is D; therefore F measures D.

And it measures C also; therefore F measures D, C; therefore it will also measure the greatest common measure of D, C. [VII.2.p.1]

But the greatest common measure of D, C is E; therefore F measures E, the greater the less: which is impossible.

Therefore no number which is greater than E will measure the numbers A, B, C; therefore E is the greatest common measure of A, B, C. Q. E. D.