Euclid’s Algorithm for GCD

Mattox Beckman

Objectives

  • Use Euclid’s algorithm to calculate the GCD of two numbers.
  • Use the extended Euclid’s algorithm to solve Linear Diophantine equations.

Euclid’s Algorithm

  • Reminder: the GCD of two numbers \(a\) and \(b\) is the largest factor \(g\) that divides both \(a\) and \(b\).
  • Notation: \(g|a\) means “\(g\) divides \(a\).”
  • To take the GCD of two numbers \(a\) and \(b\) you could just factor the numbers, but that is expensive.
  • Euclid’s algorithm is faster!

Calculating GCD with simple subtraction.

  • Let \(a\) be the largest number, let \(b\) be the smaller one. We want \(g = gcd(a,b)\)
  • Mathematical fact: If \(g|a\) and \(g|b\) then also \(g|(a+b)\) and \(g|(a-b)\)
    • So, we can recursively define \(gcd(a,b) = gcd(b,a-b)\) (when \(a>b>0\)).
    • Also \(gcd(a,0) = a\).

  • How long would this take? 

    int gcd(int a, int b) {
  if (b==0) return a;
  if (a<b) return gcd(b,a);
  return gcd(b,a-b);
}

Example 1

  • 28 = \(2\times 2\times 7\), 20 = \(2\times 2 \times 5\)
  • \(gcd(28,20) = gcd(20,8) = gcd(12,8) = gcd(8,4) = gcd(4,0) = 4\)

Euclid’s Algorithm

  • Subtraction is slow. Let’s try subtracting multiples.
    • \(gcd(a,b) = gcd(b,a-nb)\) where \(n\) is an integer and \(a-nb \ge 0\).
  • For such \(n\), notice \(r = a-nb = mod(a,b)\).
  • We know \(g|a\) and \(g|nb\).
  • Therefore, we also know \(g|r\).
  • Therefore, \(gcd(a,b) = gcd(b,mod(a,b))\).
int gcd(int a, int b) {
  if (b==0) return a;
  if (a<b) return gcd(b,a);
  return gcd(b,a % b);
}

Example: \(gcd(30,28)\)

  • 30 = 2*3*5 , 28 = 2*2*7
  • 30 = 28*1 + 2
  • 28 = 14*2 + 0
  • GCD is 2

Example: \(gcd(28,20)\)

  • 28 = 2*2*7, 20 = 2*2*5
  • 28 = 20*1 + 8
  • 20 = 8*2 + 4
  • 8 = 4*2 + 0
  • GCD is 4

Diophantine Equations

  • A Diophantine Equation is a polynomial equation where we are only interested in integer solutions.
  • Linear Diophantine equation: \(ax + by = g\),
    • Let \(g = gcd(a,b)\) for this discussion.
  • Running example: Suppose you go to the store. You buy \(x\) apples at 72 cents each and \(y\) oranges at 33 cents each. You spend $5.85. How many of each did you buy?

Calculating \(x\) and \(y\).

  • Given:
    • \(ax+by=g\)
    • \(g = gcd(a,b)\).
  • We can “Euclid Algorithm” the equation: \[bx_1 + (a\ mod\ b)y_1 = g\]

  • Get rid of modulus: \(a\ mod\ b = a - \lfloor {a\over b}\rfloor \times b\)

    \[bx_1 + (a-\lfloor{a\over b}\rfloor y_1) = g\]

  • Rearrange to get coefficients of \(a\) and \(b\):

    \[ ay_1 + b(x_1 - \lfloor {a\over b}\rfloor y_1) = g \]

  • Therefore \(x = y_1\) and \(y = x_1 - \lfloor {a\over b} \rfloor y_1\)

Source code

void extendedEuclid(int a, int b, int &x, int &y, int &d) {
   if (b == 0) {
     x = 1; y = 0; d = a; return;
   }
   extendedEuclid(b, a % b);

   int x1 = y;
   int y1 = x - (a / b) * y;

   x = x1;
   y = y1;
}

Example

Suppose you go to the store. You buy \(x\) apples at 72 cents each and \(y\) oranges at 33 cents each. You spend $5.85. How many of each did you buy?

\(a\) \(b\) \(x\) \(y\)
72 33    

r1

Suppose you go to the store. You buy \(x\) apples at 72 cents each and \(y\) oranges at 33 cents each. You spend $5.85. How many of each did you buy?

\(a\) \(b\) \(x\) \(y\)
72 33    
33 6    

r2

Suppose you go to the store. You buy \(x\) apples at 72 cents each and \(y\) oranges at 33 cents each. You spend $5.85. How many of each did you buy?

\(a\) \(b\) \(x\) \(y\)
72 33    
33 6    
6 3    

r3

Suppose you go to the store. You buy \(x\) apples at 72 cents each and \(y\) oranges at 33 cents each. You spend $5.85. How many of each did you buy?

\(a\) \(b\) \(x\) \(y\)
72 33    
33 6    
6 3    
3 0    

r4

Suppose you go to the store. You buy \(x\) apples at 72 cents each and \(y\) oranges at 33 cents each. You spend $5.85. How many of each did you buy?

\(a\) \(b\) \(x\) \(y\)
72 33    
33 6    
6 3    
3 0 1 0

r5

Suppose you go to the store. You buy \(x\) apples at 72 cents each and \(y\) oranges at 33 cents each. You spend $5.85. How many of each did you buy?

\(a\) \(b\) \(x\) \(y\)
72 33    
33 6    
6 3 0 1
3 0 1 0

r6

Suppose you go to the store. You buy \(x\) apples at 72 cents each and \(y\) oranges at 33 cents each. You spend $5.85. How many of each did you buy?

\(a\) \(b\) \(x\) \(y\)
72 33    
33 6 1 -5
6 3 0 1
3 0 1 0

r7

Suppose you go to the store. You buy \(x\) apples at 72 cents each and \(y\) oranges at 33 cents each. You spend $5.85. How many of each did you buy?

\(a\) \(b\) \(x\) \(y\)
72 33 -5 11
33 6 1 -5
6 3 0 1
3 0 1 0

r8

Suppose you go to the store. You buy \(x\) apples at 72 cents each and \(y\) oranges at 33 cents each. You spend $5.85. How many of each did you buy?

\(a\) \(b\) \(x\) \(y\)
72 33 -5 11
33 6 1 -5
6 3 0 1
3 0 1 0

\[ 72 \times -5 + 33 \times 11 = 3 \]

Result

Suppose you go to the store. You buy \(x\) apples at 72 cents each and \(y\) oranges at 33 cents each. You spend $5.85. How many of each did you buy?

  • \(72 \times -5 + 33 \times 11 = 3\)
  • Multiply both sides by 195
    • \(72 \times -975 + 33 \times 2145 = 3\)
  • We can add \(72({33\over3})n\) to the 72 term and subtract \(33({72\over 3})n\) to the 33 term.
  • Solve for n:
    • \(-975 + 11n > 0\)
  • \(n> 88.6\), so take \(n=89\).
  • Final equation:
    • \(72 \times 4 + 33 \times 9 = 585\)