45.2 THE GREATEST COMMON DIVISOR 319 Therefore no (Web hosting servers)
45.2 THE GREATEST COMMON DIVISOR 319 Therefore no number greater than F will divide A and C, so F is their greatest common divisor. Corollary. This argument makes it evident that any number dividing two numbers divides their greatest common divisor. Q.E.D. Note. Euclid s statements have been simplified here in one nontrivial respect: Greek mathematicians did not regard unity as a divisor of another positive integer. Two positive integers were either both equal to unity, or they were relatively prime, or they had a greatest common divisor. In fact, unity was not even considered to be a number, and zero was of course nonexistent. These rather awkward conventions made it necessary for Euclid to duplicate much of his discussion, and he gave two separate propositions that are each essentially like the one appearing here. In his discussion, Euclid first suggests subtracting the smaller of the two current numbers from the larger, repeatedly, until we get two numbers where one is a multiple of the other. But in the proof he really relies on taking the remainder of one number divided by another; and since he has no simple concept of zero, he cannot speak of the remainder when one number divides the other. It is reasonable to say that he imagines each division (not the individual subtractions) as a single step of the algorithm, and hence an authentic rendition of his algorithm can be phrased as follows: Algorithm E (Original Euclidean algorithm). Given two integers A and C greater than unity, this algorithm finds their greatest common divisor. El. [A divisible by C?] If C divides A, the algorithm terminates with C as the answer. E2. [Replace A by remainder.] If A mod C is equal to unity, the given numbers were relatively prime, so the algorithm terminates. Otherwise replace the pair of values (A, C) by (C, Amod C) and return to step El. 1 The proof Euclid gave, which is quoted above, is especially interesting because it is not really a proof at all! He verifies the result of the algorithm only if step El is performed once or thrice. Surely he must have realized that step El could take place more than three times, although he made no mention of such a possibility. Not having the notion of a proof by mathematical induction, he could only give a proof for a finite number of cases. (In fact, he often proved only the case n = 3 of a theorem that he wanted to establish for general n.) Although Euclid is justly famous for the great advances he made in the art of logical deduction, techniques for giving valid proofs by induction were not discovered until many centuries later, and the crucial ideas for proving the validity of algorithms are only now becoming really clear. (See Section 1.2.1 for a complete proof of Euclid s algorithm, together with a short discussion of general proof procedures for algorithms.) It is worth noting that this algorithm for finding the greatest common divisor was chosen by Euclid to be the very first step in his development of the theory of numbers. The same order of presentation is still in use today in modern