Theorems 62–79
Theorem 62 (Euclid VII.23). If two numbers be prime to one another, the number which measures the one of them will be prime to the remaining number.
Proof: Let A, B be prime to one another, and let C measure A. If C, B are not prime to one another, some number D measures them. D measures C and C measures A, so D measures A. It also measures B: which is impossible.
Theorem 63 (Euclid VII.24). If two numbers be prime to any number, their product also will be prime to the same.
Proof: Let A, B be prime to C, and let A by multiplying B make D. If C, D are not prime to one another, some number E measures them. C, A are prime to one another and E measures C, so A, E are prime to one another (Theorem 62). As many times as E measures D, so many units let there be in F. Then E by multiplying F makes D. But A by multiplying B also makes D. So the product of E, F is equal to the product of A, B, and E : A = B : F (Theorem 58). A, E are prime to one another, so they are the least in their ratio (Theorem 60), and the least measure those in the same ratio the same number of times, antecedent the antecedent and consequent the consequent (Theorem 59). So E measures B. It also measures C, and B, C are prime to one another: which is impossible.
Theorem 64 (Euclid VII.25). If two numbers be prime to one another, the product of one of them into itself will be prime to the remaining one.
Proof: Let A, B be prime to one another, and let A by multiplying itself make C. Make D equal to A. Each of D, A is prime to B, so the product of D, A is prime to B (Theorem 63). That product is C.
Theorem 65 (Euclid VII.26). If two numbers be prime to two numbers, both to each, their products also will be prime to one another.
Proof: Let A, B be prime to each of C, D. Let A by multiplying B make E, and C by multiplying D make F. A, B are each prime to C, so E is prime to C (Theorem 63). For the same reason E is prime to D. So C, D are each prime to E, and their product F is prime to E (Theorem 63).
Theorem 66 (Euclid VII.27). If two numbers be prime to one another, and each by multiplying itself make a certain number, the products will be prime to one another; and, if the original numbers by multiplying the products make certain numbers, the latter will also be prime to one another [and this is always the case with the extremes].
Proof: Let A, B be prime to one another. Let A by multiplying itself make C, and by multiplying C make D. Let B by multiplying itself make E, and by multiplying E make F. C, B are prime to one another (Theorem 64). Then, since B by multiplying itself makes E, C, E are prime to one another (Theorem 64). Again A, E are prime to one another (Theorem 64). So A, C are each prime to each of B, E, and the product of A, C, which is D, is prime to the product of B, E, which is F (Theorem 65).
Theorem 67 (Euclid VII.28). If two numbers be prime to one another, the sum will also be prime to each of them; and, if the sum of two numbers be prime to any one of them, the original numbers will also be prime to one another.
Proof: Let AB, BC be prime to one another. If CA, AB are not prime to one another, some number D measures them. It measures the whole CA and AB, so it measures the remainder BC. It also measures BA: which is impossible. Likewise for CA, BC.
Conversely, let CA, AB be prime to one another. If AB, BC are not, some number D measures them. It measures each of AB, BC, so it measures the whole CA. It also measures AB: which is impossible.
Theorem 68 (Euclid VII.29). Any prime number is prime to any number which it does not measure.
Proof: Let A be prime and not measure B. If B, A are not prime to one another, some number C measures them. C measures B and A does not, so C is not the same as A. And C measures A, which is prime, though C is not the same as A: which is impossible.
Theorem 69 (Euclid VII.30). If two numbers by multiplying one another make some number, and any prime number measure the product, it will also measure one of the original numbers.
Proof: Let A by multiplying B make C, and let the prime D measure C. Let D not measure A. Then A, D are prime to one another (Theorem 68). As many times as D measures C, so many units let there be in E. Then D by multiplying E makes C. But A by multiplying B also makes C. So D : A = B : E (Theorem 58). D, A are prime to one another, so least (Theorem 60), and the least measure those in the same ratio the same number of times, antecedent the antecedent and consequent the consequent (Theorem 59). So D measures B. Likewise, if D does not measure B, it measures A.
Theorem 70 (Euclid VII.31). Any composite number is measured by some prime number.
Proof: Let A be composite. Some number B measures it. If B is prime, what was enjoined is done. If B is composite, some number C measures it, and C measures A. If C is prime, it is done. If composite, some number measures it. If the investigation is continued in this way, some prime number will be found which measures the number before it, and which also measures A. For if it is not found, an infinite series of numbers will measure A, each less than the one before: which is impossible in numbers.
Here Euclid states the principle himself. It is Theorem 22: among numbers one is least.
Theorem 71 (Euclid VII.32). Any number either is prime or is measured by some prime number.
Proof: If A is prime, it is done. If composite, some prime number measures it (Theorem 70).
Theorem 72 (Euclid VII.33). Given as many numbers as we please, to find the least of those which have the same ratio with them.
Proof: Let them be A, B, C. If they are prime to one another, they are the least (Theorem 60). If not, let D be their greatest common measure (Theorem 43), and as many times as D measures A, B, C, so many units let there be in E, F, G. Then E, F, G measure A, B, C according to the units in D (Theorem 31), that is, the same number of times. So E, F, G are in the same ratio with A, B, C (Definition 18).
They are the least. If not, let H, K, L be less, in the same ratio. Then H measures A the same number of times that K measures B and L measures C. As many times as H measures A, so many units let there be in M. Then M measures A according to the units in H (Theorem 31), and likewise B according to K, and C according to L. So M measures A, B, C. And since H by multiplying M makes A, and E by multiplying D makes A, E : H = M : D (Theorem 58). E is greater than H, so M is greater than D. And M measures A, B, C: which is impossible, since D is their greatest common measure.
The proof supposes: that H, K, L measure A, B, C the same number of times. This is Theorem 59 if H, K, L are taken as the least, which Theorem 22 allows.
Theorem 73 (Euclid VII.34). Given two numbers, to find the least number which they measure.
Proof: Let them be A, B.
First let them be prime to one another, and let A by multiplying B make C. Then B by multiplying A makes C (Theorem 31), so A, B measure C. It is the least. If not, let them measure D, less than C. As many times as A measures D, so many units let there be in E; and as many times as B measures D, so many in F. The product of A, E is equal to the product of B, F, so A : B = F : E (Theorem 58). A, B are prime, so least (Theorem 60), so B measures E, consequent the consequent (Theorem 59). And since A by multiplying B, E makes C, D, B : E = C : D (Theorem 56). B measures E, so C measures D, the greater the less: which is impossible.
Next let them not be prime to one another. Let F, E be the least in the same ratio with A, B (Theorem 72). Then the product of A, E is equal to the product of B, F (Theorem 58). Let it be C. A, B measure C. It is the least. If not, let them measure D, less than C. As many times as A measures D, so many units let there be in G; and as many times as B measures D, so many in H. The product of A, G is equal to the product of B, H, so A : B = H : G (Theorem 58). But A : B = F : E, so F : E = H : G. F, E are least, so E measures G (Theorem 59). And since A by multiplying E, G makes C, D, E : G = C : D (Theorem 56). E measures G, so C measures D, the greater the less: which is impossible.
Theorem 74 (Euclid VII.35). If two numbers measure any number, the least number measured by them will also measure the same.
Proof: Let A, B measure CD, and let E be the least that they measure. If E does not measure CD, let E, measuring DF, leave CF less than itself. A, B measure E and E measures DF, so A, B measure DF. They measure the whole CD, so they measure the remainder CF, which is less than E: which is impossible.
Theorem 75 (Euclid VII.36). Given three numbers, to find the least number which they measure.
Proof: Let them be A, B, C. Let D be the least number measured by A, B (Theorem 73).
If C measures D, then A, B, C measure D. It is the least: if they measured E, less than D, then A, B would measure E, so D would measure E (Theorem 74), the greater the less: which is impossible.
If C does not measure D, let E be the least number measured by C, D (Theorem 73). A, B measure D and D measures E, so A, B, C measure E. It is the least: if they measured F, less than E, then A, B would measure F, so D would measure F (Theorem 74); and C measures F; so C, D measure F, and E measures F (Theorem 74), the greater the less: which is impossible.
Theorem 76 (Euclid IX.20). Prime numbers are more than any assigned multitude of prime numbers.
Proof: Let A, B, C be the assigned primes. Take the least number DE measured by A, B, C (Theorem 75), and add the unit DF. EF is either prime or not. If prime, then A, B, C, EF are primes more than A, B, C. If not, some prime G measures it (Theorem 70). G is none of A, B, C: for if it were, it would measure DE; it also measures EF; so it would measure the remaining unit DF: which is absurd. So A, B, C, G are primes more than the assigned multitude.
Euclid does not say the primes are infinite. He says that for any multitude of them there is one more. This is the rule of the whole work: "any," not "all."
Theorem 77 (Euclid IX.14). If a number be the least that is measured by prime numbers, it will not be measured by any other prime number except those originally measuring it.
Proof: Let A be the least number measured by the primes B, C, D. If possible, let the prime E, none of B, C, D, measure A, according to F. Each of B, C, D measures the product of E, F, so each measures E or F (Theorem 69). They do not measure E, which is prime and not the same as any of them. So they measure F, which is less than A: which is impossible.
Theorem 78 (Euclid IX.30). If an odd number measure an even number, it will also measure the half of it.
Proof: Let the odd A measure the even B according to C. C is not odd; otherwise B would be odd (Theorem 40). So C is even, and A measures B an even number of times. So it measures the half of B.
Theorem 79 (Euclid IX.31). If an odd number be prime to any number, it will also be prime to the double of it.
Proof: Let the odd A be prime to B, and C be double of B. If A, C are not prime to one another, some number D measures them. A is odd, so D is odd. D, being odd, measures the even C, so it measures its half B (Theorem 78). So D measures A, B, which are prime to one another: which is impossible.