The Greatest Common Divisor

For $a$ and $b$, the number $(a,b)$ is the largest number which divides $a$ and $b$ evenly.

$$(56,98)=14\qquad(76,190)=38$$

Theorem 1   For any $a,b$ there are integers $x,y$ with $ax+by=(a,b)$

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

It is easy to see that $x''=1$, $y'=0$ is a solution to the final equation and we get a solution to the original equation by working backwards:

$$x'=x''-3y'=1\quad y=y'-3x'=-3\quad x=x'-2y=7\quad\vrule height 8pt width 4pt$$

We could also solve an equation like $30x+69y=15$ by multiplying our solution: $y=-15=5(-3)$, $x=35=5(7)$. 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 $(30,69)=3$.

All other integer solutions of $30x+69y=15$ may be obtained by changing the first solution:

$$y=-15+\frac{30}3t\quad x=35-\frac{69}3t\quad\hbox{for $t$ integer}$$

If we do the process illustrated on the previous page for any equation $ax+by=(a,b)$, we eventually get one of the coefficients as zero and the other as $(a,b)$. [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 $a$ and $b$ are several hundred digits long. It is easy to show that the larger of the two coefficients decreases by at least $1/2$ every two equations, hence that in twenty equations the larger coefficient has decreased by $2^{-10}<10^{-3}$, 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, $ar\equivas\hbox{ (mod }p)$, and $a\not\equiv 0$, then $r\equiv s$.

Proof: Since $p$ is a prime, $(a,p)=1$, so Theorem 1 says there are integer $x,y$ with $ax+py=1$. Hence

$$ax\equiv1\hbox{ (mod }p)\quad\hbox{and}\quad r\equiv(1)r\equi... ...equiv xas\equivs\hbox{ (mod }p)\quad\vrule height 8pt width 4pt$$

Corollary 3   If p is a prime number and $a\not\equiv 0$ mod $p$, then for any $b$, there is $y$ with $ay\equivb\hbox{ (mod }p)$.

Proof: We showed in the preceding proof that there is $x$ with $ax\equiv1\hbox{ (mod }p)$. Let $y=bx$. height 8pt width 4pt

Corollary 4 (The ``Chinese Remainder Theorem'')   If $(p,q)=1$, then for any $a,b$, there is an $n$ with

$$n\equiva\hbox{ (mod }p)\quad \hbox{and}\quad n\equivb\hbox{ (mod }q)$$

Proof: Theorem 1 implies there are integers $x,y$ such that

$$px+qy=b-a\quad\hbox{so let }n=px+a\quad\vrule height 8pt width 4pt$$