Abstract Algebra - Math 4010
Computing gcd and more

Preamble: If $d \in \ensuremath{\mathbb{Z}}^{*}$ divides $a \in \ensuremath{\mathbb{Z}}$, then $\pm d$ divides $\pm a$. We may as well assume that $d \geq 1$ and that $a \geq 0$. Note that 0 is divisible by any integer, so saying that $d$ divides both $a >0$ and 0 is equivalent to saying that $d$ divides $a$. It makes sense to restrict ourselves to positive integers only. Then defining $\gcd(a,b)$ to be the greatest integer that divides both $a$ and $b$ makes sense for $a, b \in \ensuremath{\mathbb{Z}}^{+}$, since at least one integer, $1$, divides both $a$ and $b$ and the possibilities are finite since $\gcd(a,b) \leq \min \{a,b\}$.

Simple things: If $a$ divides $b$, then $\gcd(a,b) = a$. If $p$ is a prime number and $1 \leq a < p$, then $\gcd(a,p) = 1$. When $\gcd(a,b) = 1$, we say that $a$ and $b$ are relatively prime.

In class, I showed how the greatest common divisor of any two positive integers could be computed in a systematic way. I also alluded to the fact that the computations could also be used to solve a certain equation. That is, if $d = \gcd(a,b)$, then there are integers, $m$ and $n$ such that $ma + bn = d$. Note that $(m+bk)a + (n-ak)b = d$ is also a solution for all $k \in \ensuremath{\mathbb{Z}}$.

To make the notation work out nicely, we rename $a$ and $b$ as $a_0$ and $a_1$, and assume that $1 \leq a_1 \leq a_0$. We define $m_1$ to be the greatest integer $\leq \displaystyle \frac{a_0}{a_1}$, and $a_2$ to be the remainder. That is:

$$a_0 = m_1a_1 + a_2,$$

where $0 \leq a_2 < a_1$. $m_1$ and $a_2$ are uniquely defined. We can define a sequence of numbers as follows. As long as $a_{k+1} > 0$, we can define $m_{k+1}$ and $a_{k+2}$ by dividing $a_{k}$ by $a_{k+1}$ and taking the remainder. That is,

$$a_k = m_{k+1}a_{k+1} + a_{k+2}.$$

Notice that the $a_k$ sequence is strictly decreasing. For some $n \geq 1$, $a_{n+1} = 0$ and we can't go further. Then $a_n = \gcd(a_0,a_1)$, as noted in class, since $\gcd(a_{k-1},a_k) = \gcd(a_k,a_{k+1})$ for $1 \leq k \leq n$. The last pair is $a_n$ and 0, with a greatest common divisor of $a_n$, as noted above. Also note that $n = 1$ if we start with a trivial case such as $a_1 = 1$ or $a_0 = a_1$, since the first remainder, $a_2$, would be 0.

Now define a sequence of integers, $b_k$, for $0 \leq k \leq n+1$ as follows. $b_{n+1} = 1$ and $b_{n} = 0$. For $1 \leq k \leq n$, let

$$b_{k-1} = b_{k}m_k + b_{k+1}.$$

Note how the $a_k$ and $b_k$ sequences satisfy the same recursion. They differ because $a_n = d$ and $a_{n+1} = 0$, whereas $b_n = 0$ and $b_{n+1} = 1$.

Note that $a_nb_{n+1} - a_{n+1}b_n = a_n \times 1 - 0 \times 0 = a_n = \gcd(a_0,a_1)$. That is,

$$a_kb_{k+1} - a_{k+1}b_k = \gcd(a_0,a_1)$$

for $k=n$. It turns out that this is true for all $k$ between 0 and $n$, so that

$$a_{0}b_{1} - a_{1}b_{0} = \gcd(a_0,a_1).$$

How can this be proved? The easiest way is to use $2 \times 2$ matrices to avoid messy calculations. Let $d = \gcd(a_0,a_1)$ and $$\mathbf{D} = \left(\begin{array}{cc} d & 0 \\ 0 & 1 \end{array}\right)$$. For $1 \leq k \leq n$, let $$\mathbf{M}_{k} = \left(\begin{array}{cc} m_{k} & 1 \\ 1 & 0 \end{array}\right)$$. Note that $\det{\mathbf{D}} = d$ and that $\det{\mathbf(M)_{k}} = -1, \: \forall \: k$. Finally, let $$\mathbf{A}_{k} = \left(\begin{array}{cc} a_{k} & b_{k} \\ a_{k+1} & b_{k+1} \end{array}\right)$$ for $0 \leq k \leq n$. Note that $\mathbf{A}_{n} = \mathbf{D}$, and for $1 \leq k \leq n$, it is easy to compute

$$\begin{array}{lcl} \mathbf{M}_{k}\mathbf{A}_{k} & = & \left(\... ...{k} \end{array}\right) \\ & = & \mathbf{A}_{k-1}. \end{array}$$

This means that $$\mathbf{A}_{0} = \mathbf{M}_{1}\mathbf{A}_{1} = \mathbf{M}_{1}\mathbf{M}_{2}\mathbf{A}_{2} \dots$$, giving $$\left(\begin{array}{cc} a_{0} & b_{0} \\ a_{1} & b_{1} \end{array}\right) = \prod_{k=1}^{n} \mathbf{M}_{k} \mathbf{D}$$. Also, $\det{\mathbf{A}_{0}} = (-1)^{n}d$. Thus $$a_{0}b_{1} - a_{1}b_{0} = (-1)^{n}d$$. If $n$ is even, $$a_{0}b_{1} + a_{1}(-b_{0}) = d$$ and if $n$ is odd, $$a_{0}(-b_{1}) + a_{1}b_{0} = d$$.

The methods described above solve the problem of computing the greatest common divisor, $d$, of two positive integers and of expressing $d$ as a ``linear combination'' of these two integers.

Example: Compute gcd(2147483647,4372893)

Solution:

 2147483647 = 491 * 4372893 + 393184
    4372893 =  11 * 393184 + 47869
     393184 =   8 * 47869 + 10232
      47869 =   4 * 10232 + 6941
      10232 =   1 * 6941 + 3291
       6941 =   2 * 3291 + 359
       3291 =   9 * 359 + 60
        359 =   5 * 60 + 59
         60 =   1 * 59 + 1
         59 =  59 * 1 + 0

n = 10 and the gcd of  2147483647 and  4372893 is  1, the last
non-zero remainder.

Values of b(k)

 k  b(k-1) = m(k) * b(k) + b(k+1)

10  1 = 59 * 0 + 1
 9  1 = 1 * 1 + 0
 8  6 = 5 * 1 + 1
 7  55 = 9 * 6 + 1
 6  116 = 2 * 55 + 6
 5  171 = 1 * 116 + 55
 4  800 = 4 * 171 + 116
 3  6571 = 8 * 800 + 171
 2  73081 = 11 * 6571 + 800
 1  35889342 =  491 * 73081 +  6571

Finally:

   2147483647 * 73081 + 4372893 * -35889342 = 1