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 =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 thegcd(a, b)

*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:

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 (Formodm)

*and*

**e***known, you can simply run our*

**m***Extended Euclidean Algorithm,*with (

*a, b*) = (

*e, m*), witch will give us:

e.x + m.y = 1

e.x ≡ 1 (modm)

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

n = 2047 = 23 * 89

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

e = 179We want to find

*, witch satisfy:*

**d**e.d ≡ 1 (Applying the above algorithm we get:modm)

1936 * 141 + 179 * -1525 = 1

⇒ 179 * -1525 ≡ 1 (mod1936)

⇒ d = 411

since: -1525 ≡ 411 (This is exactly the example we used here!mod1936)

### 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

**and***a**b*. So we can write:a = y.b + r

for y = ⌋|a| / |b|⌊Now, if r = 0, we have:

a = y.b ⇔If |r| > 0, we have:gcd(a, b) = b.

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

⇒ 0 ≡ rmod(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

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***times until we get r = 0, let's call***n**a = r*_{1 }and*:***b = r**_{2}(1) r_{1}= y_{1}.r_{2}+ r_{3}

(2) r_{2}= y_{2}.r_{3}+ r_{4}

(3) r_{3}= y_{3}.r_{4}+ r_{5}

...

(i) r_{i}= y_{i}.r_{i+1}+ r_{i+2}

...

(n) rAs we can see, y_{n}= y_{n}.r_{n+1}

_{i }is an integer defined by:yAnd as pointed in the first proof:_{i}= ⌋|r_{i}| / |r_{i+1}|⌊

gcd(a, b) = rLet's obtain_{n}

*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(rWe can go back, for step (n - 3) and go on until we get_{n-2},r_{n-3}) = r_{n}

*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) = 2Observe that the pair (x, y) is not unique, since:

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