Next: Powers modulo a prime Up: Introduction to Number Theory Previous: Congruences   Contents

## The Greatest Common Divisor

For and , the number is the largest number which divides and evenly.

Theorem 1   For any there are integers with

Proof: The equation can be solved by making a sequence of simplifying substitutions:

It is easy to see that , is a solution to the final equation and we get a solution to the original equation by working backwards:

We could also solve an equation like by multiplying our solution: , . It should be clear that the equation will have no solution in integers if 15 is replaced by something that is not a multiple of .

All other integer solutions of may be obtained by changing the first solution:

If we do the process illustrated on the previous page for any equation , we eventually get one of the coefficients as zero and the other as . [In fact, this process is usually presented as Euclid's algorithm for finding the greatest common divisor.'']

It is important that this process is feasible [on a computer] even if and are several hundred digits long. It is easy to show that the larger of the two coefficients decreases by at least every two equations, hence that in twenty equations the larger coefficient has decreased by , so a 600-digit number would not require more than 4000 equations. [this analysis can be improved]

We pointed out earlier that division does not work with congruences. An important application of Theorem 1 is that it does work for prime numbers.

Corollary 2   If p is a prime number, , and , then .

Proof: Since is a prime, , so Theorem 1 says there are integer with . Hence

Corollary 3   If p is a prime number and  mod , then for any , there is with .

Proof: We showed in the preceding proof that there is with . Let . height 8pt width 4pt

Corollary 4 (The Chinese Remainder Theorem'')   If , then for any , there is an with

Proof: Theorem 1 implies there are integers such that

Next: Powers modulo a prime Up: Introduction to Number Theory Previous: Congruences   Contents
Translated from LaTeX by Scott Sutherland
2002-12-14