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:

$$\begin{eqnarray*}30x+69y&=&3\ 30x'+9y&=&3\quad[x'=x+2y]\\ 3x'+9y'&=&3\quad[y'=y+3x']\ 3x''+0y'&=&3\quad[x''=x'+3y']\end{eqnarray*}$$

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\mbox{\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}{3}t\quad x=35-\frac{69}{3}t\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}\equiv{as}\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}\equiv{1}\hbox{ (mod }{p})\quad\hbox{and}\quad r{\equiv}(... ...quiv{s}\hbox{ (mod }{p})\quad\mbox{\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}\equiv{b}\hbox{ (mod }{p})$.

Proof: We showed in the preceding proof that there is $x$ with ${ax}\equiv{1}\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}\equiv{a}\hbox{ (mod }{p})\quad \hbox{and}\quad{n}\equiv{b}\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\mbox{\vrule height 8pt width 4pt}$$