unless both and are 0 in which case .
If , the greatest common divisor exists because if then , and there are only positive integers . Similarly, the exists when .
Assume for the moment that we have already proved Theorem 1.1.6. A natural (and naive!) way to compute is to factor and as a product of primes using Theorem 1.1.6; then the prime factorization of can read off from that of and . For example, if and , then and , so . It turns out that the greatest common divisor of two integers, even huge numbers (millions of digits), is surprisingly easy to compute using Algorithm 1.1.13 below, which computes without factoring or .
To motivate Algorithm 1.1.13, we compute in a different way. First, we recall a helpful fact.
To prove uniqueness, suppose for the sake of contradiction that and also satisfy the conclusion but that . Then since , so and we can write for some . But then since , a contradiction.
For us an algorithm is a finite sequence of instructions that can be followed to perform a specific task, such as a sequence of instructions in a computer program, which must terminate on any valid input. The word ``algorithm'' is sometimes used more loosely (and sometimes more precisely) than defined here, but this definition will suffice for us.
We use the division algorithm repeatedly to compute . Dividing by we find that
so and . Notice that if a natural number divides both and , then divides their difference and still divides . On the other hand, if divides both and , then it has to divide their sum as well! We have made progress:
This equality also follows by repeated application of Lemma 1.1.9. Repeating, we have
so . Keep going:
Aside from some tedious arithmetic, that computation was systematic, and it was not necessary to factor any integers (which is something we do not know how to do quickly if the numbers involved have hundreds of digits).
sage: gcd(97,100) 1 sage: gcd(97 * 10^15, 19^20 * 97^2) 97
so by induction . Since , this proves the lemma.
At this point it would be natural to formally analyze the complexity of Algorithm 1.1.13. We will not do this, because the main reason we introduced Algorithm 1.1.13 is that it will allow us to prove Theorem 1.1.6, and we have not chosen to formally analyze the complexity of the other algorithms in this book. For an extensive analysis of the complexity of Algorithm 1.1.13, see [#!knuth2!#, §4.5.3].
With Algorithm 1.1.13, we can prove that if a prime divides the product of two numbers, then it has got to divide one of them. This result is the key to proving that prime factorization is unique.
You might think this theorem is ``intuitively obvious'', but that might be because the fundamental theorem of arithmetic (Theorem 1.1.6) is deeply ingrained in your intuition. Yet Theorem 1.1.19 will be needed in our proof of the fundamental theorem of arithmetic.
William 2007-06-01