Notes on Greatest Common Divisors

2014, Kenneth Levasseur
Mathematical Sciences
UMass Lowell
Kenneth_Levasseur@uml.edu

Import["http://mirrors.creativecommons.org/presskit/buttons/88x31/png/by-nc-sa.eu.png",ImageSize->128]

Divisibility, Greatest common divisor

One of the distinctive properties of the set of integers, {…, -2, -1, 0, 1, 2,…} is that if you divide a positive number into any integer, you will get a unique quotient and remainder.  More precisely, if you divide b (b>0) into a, there will be integers q and r such that a = b q + r and 0≤r<b.     We will take this as given, but it can be proven by mathematical induction.

If r=0, i. e.,  a = b q,  then all of the following say the same thing
			b divides a
			a is a multiple of b
			b is a factor of a
			b is a divisor of a

gcd(a,b) is the largest positive integer that is a divisor of both a and b.

In Mathematica you can get the gcd of two numbers using the function GCD:

?GCD

GCD[1001,231]

More information can be obtained with ExtendedGCD

?ExtendedGCD

ExtendedGCD[1001,231]

We'll see what the second item in this output represents below.

The Euclidean Algorithm

The Euclidean Algorithm is based on the following properties of the greatest common divisor

	gcd(a,0)= a   for a≠0
	gcd(a, b)= gcd(b, r)   if b≠0   and  a = b q + r
	
To compute gcd(a,b), we divide b into a and get a remainder r such that 0≤ r<|b|.  By the property above, gcd(a, b)= gcd(b, r) .  We repeat the process until  we get zero for a remainder.  The last nonzero number that is the second entry in our pairs is the greatest common divisior.   This is inevitable because the second number in each pair is smaller than the previous one.

Here is the computation to verify that gcd(99, 53) = 1 using a table.   At each line, the “r-value”  is divided the number above it.   The quotient is placed on that line, next to “r”  while and the remainder placed in the next line of the r column.

EuclidTable[99,53]

If you were allowed to pick two numbers less than 1000, which would you pick in order to force Euclid to work hardest?   Here's a hint

EuclidTable[34,21]

Related web site:
   UML Extended Euclidean Algorithm WebMathematica Page

The "a s + b t = gcd(a,b) Theorem"

For fixed values of a and b, consider integers of the form a x+b y where x and y can be any two integers.  For example if a = 36 and b = 27,  some of these results are tabulated below with x values along the left column and the y values on top.

Notice any patterns?   What is the smallest positive value the you see in this table?  How is it connected to 36 and 27

Theorem.  If a and b are positive integers, the smallest positive value of a x + b y  is the greatest common divisor of a and b, gcd(a,b).

Proof: If  g = gcd(a, b), then g|a  and  g|b  =>g|(a x + b y) for any x and y, so a x + b y can't be less than g.  To show that g is exactly the least positive value, we show that g can be attained by extending the Euclidean Algorithm.  Performing the extended algorithm involves building a table of numbers. There are many variations on the way that this table arranged, so if your book has this algorithm it may look slightly different.

The table for gcd(152,53) is below.   In the "r" column, you will find 152 and 53, and then the successive remainders from division.  So each number in "r" after the first two is the remainder after dividing the number immediately above it into the next number up.  To the left of each remainder is the quotient from the division.   So in this case the third row of the table tells us that 152 = 53 2 + 46. The last nonzero value in r is the greatest common divisor.

The "s" and "t" columns are new.  The values of s and t in each row are maintained so that
152s + 53t is equal to the number in the "r" column.   Notice that
		152 = 152 1+ 53 0
	53 =152 0 + 53 0
	46 = 152 1 + 53 (-2)
	...
	1 = 152 15 + 53 (-43)
	0 = 152 (-53) + 53 152

The next-to-last equation is what we're looking for in the end!  The main problem is to identify how to determine these values after the first two rows.  The first two rows in these columns will always be the same.

Let's look at the general case of computing gcd(a,b).  If the s and t values in rows i - 1 and  i - 2 are correct, we have

(A)       {({{a (Subscript[s, i-2])+b (Subscript[t, i-2])=(Subscript[r, i-2])}, {a (Subscript[s, i-1])+b (Subscript[t, i-1])=(Subscript[r, i-1])}})

In addition,we know that

(Subscript[r, i-2])=(Subscript[r, i-1]) (Subscript[q, i])+(Subscript[r, i])   \[Implies]    (Subscript[r, i])=(Subscript[r, i-2])-(Subscript[r, i-1]) (Subscript[q, i])

If you substitute the expressions for (Subscript[r, i-1]) and (Subscript[r, i-2]) from (A) into this last equation and then collect the a and b terms separately you get 
	(Subscript[r, i])= a((Subscript[s, i-2])- (Subscript[q, i])(Subscript[s, i-1])) + b((Subscript[t, i-2]) - (Subscript[q, i])(Subscript[t, i-1]))

or 
	(Subscript[s, i ])=(Subscript[s, i-2])- (Subscript[q, i])(Subscript[s, i-1])     and   (Subscript[t, i])= (Subscript[t, i-2]) - (Subscript[q, i])(Subscript[t, i-1])

Look closely at the equations for (Subscript[r, i]), ({{(Subscript[s, i]),, and  (Subscript[t, i])}}).  Their forms are all the same.  With a little bit of practice you should be able to compute s and t values quickly.

General solution to  gcd(a,b)=a x+b y

Linear Equation Theorem.  If a, b are nonzero integers such that g=gcd(a,b)=a s+b t, then the general solution to a x+b y=g is 
				(x,y)=(s+((n b)/g),t-((n a)/g))

Notes:  
One solution exists by the Extended Euclidean Algorithm.  This particular  solution and the general solution to a x+b y = 0  provides the general solution to ax+by =g. 

The values  ±(b/g) and ±(a/g)will always appear in the last row of the Extended Euclidean Algorithm table.

Example.  Solve 1972x + 1492y = gcd(1972,1492).

Therefore the general solution to 1972 x + 1492 y = 4 is (x, y) = (-115+373n,152-493n), where n is any integer.

Mathematica  Code

This is some of the Mathematica  code that was use to generate some of the material in this document.

eucliditerate={{pred___,{q0_,a0_,b0_}}:>{pred,{q0,a0,b0},{q1=Quotient[a0,b0],b0,Mod[a0,b0]}}/;b0=!=0};
EuclidTable[a_,b_]:=({{"-",a,b}}//.eucliditerate//#[[All,{1,2}]]&)//Prepend[#,{"q","r"}]&//TableForm;

EuclidTable[99,53]

Fib[0]=Fib[1]=1;
Fib[n_]:=Fib[n]=Fib[n-1]+Fib[n-2];


iterate={{pred___,{q0_,a0_,s0_,t0_},{q1_,a1_,s1_,t1_}}:>
		{pred,{q0,a0,s0,t0},
		      {q1,a1,s1,t1},
         	  {q2=Quotient[a0,a1],
         	   Mod[a0,a1],
         	   s0-q2 s1,
         	   t0-q2 t1}}/;a1=!=0};
         	   
GCDTable[a_,b_]:=
({{"-",a,1,0},{"-",b,0,1}}//.iterate)//
  Prepend[#,{"q","r","s","t"}]&//TableForm;