Euclidean Algorithm, JavaScript and Proof

In this post we will present a JavaScript implementation of the Euclidean Algorithm, and present a proof of its correctness.

Introduction

 The Euclidean Algorithm, was published in "Elements" (300 B.C. !!!), by the Greek mathematician Euclid. It is one of the oldest algorithms that still in use. It is a method to compute the greatest common divisor, and find multiplicative inverses in modular arithmetic.

Some action first

   Here we present a simple JavaScript implementation:

function gcd(a, b){
 a = a * (a < 0 ? -1 : 1); 
 b = b * (b < 0 ? -1 : 1); 

 if (b > a)
  return gcd (b, a);
 else if (b == 0)
  return a;
 else 
  return gcd (b, a % b);  
}

  Let's try to use this code, just put some numbers and see the result:

gcd(, )

 That's a simple application, this algorithm is useful in cryptography to find multiplicative inverses in modular arithmetic, so with a little extra complexity, we can put a richer algorithm in action.
 This is the so called Extended Euclidean Algorithm, we have the Bézout's identity, witch states that for every pair of integers (a, b) we have a pair of integers (x, y) witch satisfy:

a.x + b.y = gcd (a, b)

  So our next step is to present an algorithm that given a pair of integers (a, b) it returns the gcd(a, b) and the pair of integers (x, y) witch satisfy the Bézout's identity, here is our code:

function extended(a, b, obj){
 var i = (a < 0 ? -1 : 1);
 var j = (b < 0 ? -1 : 1);

 a *= i;
 b *= j;

 obj.x = 1;
 obj.y = 1;

 if (b > a)
  var result = extended (b, a, obj);
 else if (b == 0)
  var result = a;
 else {
  var result = extended (b, a % b, obj); 
  var tmp = obj.y;
  obj.y = -obj.y * Math.floor(a / b) + obj.x; 
  obj.x = tmp;
 }

 if (b > a){
  var tmp = obj.y;
  obj.y = obj.x;
  obj.x = tmp;
 }
 obj.x *= i;
 obj.y *= j;

 return result;
}

 So here are our Extended Euclidean Algorithm in action:

a:

b:

As an example we can see an application to cryptography, suppose you want to solve this equation, for d:

gcd(e, m) = 1

e.d ≡ 1 (mod m)

 For e and m known, you can simply run our Extended Euclidean Algorithm, with (a, b) = (e, m), witch will give us:

e.x + m.y = 1

e.x ≡ 1 (mod m) 

d ≡ x (mod m) 

 This equation arises naturally in some cryptography systems, like RSA, and solve it is part of it's implementation. Let's see an example:

n = 2047 = 23 * 89

m = (23 - 1) * (89 - 1) = 1936

e = 179

 We want to find d, witch satisfy:

e.d ≡ 1 (mod m)

 Applying the above algorithm we get:

1936 * 141 + 179 * -1525 = 1

 ⇒ 179 * -1525 ≡ 1 (mod 1936)

 ⇒ d = 411 

since: -1525 ≡ 411 (mod 1936)

 This is exactly the example we used here!

Proof of Correctness

 Now we want to proof that the Euclidean Algorithm is correct! Let's first assume that:

|a| ≥ |b| 

 This can always be done, without loss of generality, simple if |b| > |a|, change what we call a and b. So we can write:

a = y.b + r

for y = ⌋|a| / |b|⌊

 Now, if r = 0, we have:

 a = y.b ⇔ gcd(a, b) = b.

 If |r| > 0, we have:

a = y.b + r ⇒  a ≡ y.b + r mod(gcd(a, b)) 

⇒  0 ≡  r mod(gcd(a, b)) ⇒ gcd(a, b)  = gcd(b, r)

 Since |r| < |b|, if we repeat |b| or less this operation, we will get |r| = 0, and the algorithm always finish. So we conclude our proof.

 Now let's give a proof for the Bézout's identity, witch states that for any pair of integers (a, b) we have a pair of integers (x, y) that satisfy:

a.x + b.y = gcd (a, b)

  So let's apply the Euclidean Algorithm n times until we get r = 0, let's call a = r₁ and b = r₂:

(1) r₁ = y₁.r₂ + r₃

(2) r₂ = y₂.r₃ + r₄

(3) r₃ = y₃.r₄ + r₅

...

(i) r_i = y_i.r_i+1 + r_i+2

... 

(n) r_n = y_n.r_n+1

  As we can see, y_i is an integer defined by:

y_i = ⌋|r_i| / |r_i+1|⌊

  And as pointed in the first proof:

gcd(a, b) = r_n

  Let's obtain Bézout's identity for step (n -2):

r_n-2 = y_n-2.r_n-1 + r_n 

⇒ r_n-2 - y_n-2.r_n-1 = r_n  

⇒ r_n-2 - y_n-2.(r_n-3 - y_n-3.r_n-2) = r_n 

 ⇒ r_n-2.(1 + y_n-2.y_n-3) - y_n-2.r_n-3 = r_n 

⇒ r_n-2.x + r_n-3.y = gcd(r_n-2,r_n-3) 

with x = (1 + y_n-2.y_n-3)

and y = - y_n-2

and gcd(r_n-2,r_n-3) = r_n

 We can go back, for step (n - 3) and go on until we get a and b, it's clear that this is not a formal proof, we have to make an inductive proof, since I'm a physicist I will give an example and omit the formal proof, let's apply this stuff for gcd(746, 102):

(1a) 746 = 102 * 7 + 32

(2a) 102 = 32 * 3 + 6

(3a) 32 = 6 * 5 + 2

(3b) 32 - 6 * 5 = 2

(2b) 32 - (102 - 32 * 3) * 5 = 2 ⇒ 102 * (-5) + 32 * 16 = 2

(1b) 102 * (-5) + (746 - 102 * 7) * 16 = 2 ⇒ 746 * 16 + 102 * (-117) = 2

 Observe that the pair (x, y) is not unique, since:

746 * (-35)  + 102 * 256 = 2