Home > CS178 > Homework 6 > Multiplicative Inverse

Curby's Guide to Calculating the GCD and Multiplicative Inverse

2003-05-08 Changes:
Made the GCD calculation clearer
Changed % to mod because % is different than mod in some programming languages
First job is to find the GCD. We can accomplish this using the Euclidean method. Each step of the Euclidiean method is a line of the form: 
dividend = quotient * divisor + remainder
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.

While performing the Euclidian method, it's important to save the quotients. Here's an example, with the quotients highlighted in red: 
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
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. 
Q = { 2, 1, 3, 4, 1, 1, 3, 1 }
We're gonna now build up a new array. We can call it P. Let P[0]=0 and P[1]=1. 
GCD is 1.  Searching for multiplicative inverse:
Step 0: 0
Step 1: 1
Now we will add to P a value for every number in Q. It's defined like this: 
for i from 2 to Q.size() + 1
  P[i] = (P[i-2] - P[i-1]*Q[i-2]) mod m
Specifically, ... 
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
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.)

Top | Home > CS178 > Homework 6 > Multiplicative Inverse