VII.23

If two number be prime to one another, the number which measures the one of them will be prime to the remaining number.

Let A, B be two numbers prime to one another, and let any number C measure A; I say that C, B are also prime to one another.

For, if C, B are not prime to one another, some number will measure C, B.

Let a number measure them, and let it be D.

Since D measures C, and C measures A, therefore D also measures A.

But it also measures B; therefore D measures A, B which are prime to one another: which is impossible. [VII.def.12]

Therefore no number will measure the numbers C, B.

Therefore C, B are prime to one another. Q. E. D.