**2003-05-08 Changes:**- Made the GCD calculation clearer
- Changed % to mod because % is different than mod in some programming languages

In each step after the first, the dividend is the last divisor, and the divisor is the last remainder. If the last sentence was confusing, read it again. If it's still confusing, refer to the example below and see where values are repeated.

dividend = quotient * divisor + remainder

While performing the Euclidian method, it's important to save the quotients. Here's an example, with the quotients highlighted in red:

Stop when the remainder would be zero. The last divisor (or the last nonzero remainder) would be the GCD. We're left with a remainder of 1 (highlighted in green), meaning that the GCD is 1. In other words, these numbers are relatively prime. If the GCD is greater than 1, that means the numbers aren't relatively prime, and you would then stop the algorithm. Since in this case they're ok, we continue. Remember those values we saved? Let's call that the Q array.

Finding GCD(654,1807): Step 0: 1807 = 2 * 654 + 499 Step 1: 654 = 1 * 499 + 155 Step 2: 499 = 3 * 155 + 34 Step 3: 155 = 4 * 34 + 19 Step 4: 34 = 1 * 19 + 15 Step 5: 19 = 1 * 15 + 4 Step 6: 15 = 3 * 4 + 3 Step 7: 4 = 1 * 3 + 1 3 = 3 * 1 + 0

We're gonna now build up a new array. We can call it P. Let P[0]=0 and P[1]=1.

Q = { 2, 1, 3, 4, 1, 1, 3, 1 }

Now we will add to P a value for every number in Q. It's defined like this:

GCD is 1. Searching for multiplicative inverse: Step 0: 0 Step 1: 1

Specifically, ...

for i from 2 to Q.size() + 1 P[i] = (P[i-2] - P[i-1]*Q[i-2]) mod m

So the last value is our multiplicative inverse (green number)! (Yeah if you're implementing this, you don't actually have to keep all those values in the arrays. This page was meant to show what the math is doing. Now that you understand that, you can use m4d h4cking sk1llz to make a much more efficient version.)

Step 2: (0 - 1 * 2) mod 1807 = 1805 Step 3: (1 - 1805 * 1) mod 1807 = 3 Step 4: (1805 - 3 * 3) mod 1807 = 1796 Step 5: (3 - 1796 * 4) mod 1807 = 47 Step 6: (1796 - 47 * 1) mod 1807 = 1749 Step 7: (47 - 1749 * 1) mod 1807 = 105 Step 8: (1749 - 105 * 3) mod 1807 = 1434 Step 9: (105 - 1434 * 1) mod 1807 = 478 Multiplicative inverse of 654 (mod 1807) = 478

Top | Home > CS178 > Homework 6 > Multiplicative Inverse