Procedure to compute a multiplicative inverse

[dodo]

I think I found a procedure (other than the extended Euclidean algorithm) to compute the multiplicative inverse of a number; possibly a simpler method. It goes like this:

***EDIT: Ah, dang. I made a mistake. It will only work for a prime modulus.

Suppose we need to find $x$ satisfying $ax \equiv 1 \pmod m$, where $\gcd(a,m)=1$.

We need to use a twisted version of the division algorithm, one that gives us integers $q_1, r_1$ such that $m = q_1 a - r_1$ (note the minus sign), with $r_1$ as small as possible. (So $q_1=\lfloor m/a \rfloor+1$.) Hence, $q_1 a \equiv r_1 \pmod m$.

Now, if $r_1=1$ we would be done: $q_1$ would be the multiplicative inverse we are looking for. So suppose it is not yet. But... if we had the multiplicative inverse of $r_1$, then we could multiply it to $q_1$ to get our solution.

So... rinse and repeat: find the inverse of $r_1$ (a smaller number, now). Note that $\gcd(r_1,m)=1$ (<-- only guaranteed when $m$ is prime!), so that the procedure can in fact be repeated.

Using the same procedure repeatedly, we obtain a sequence of divisors $q_1, q_2, ..., q_n$ until $r_n=1$; then the multiplicative inverse of $a$ is the product of all $q_1, q_2, ..., q_n$ (reduce it modulo $m$ if you wish).

Here is a worked example. Suppose you want the inverse of 1234567 modulo 3257269. We proceed as follows:
3257269 = 3 . 1234567 - 446432
3257269 = 8 . 446432 - 314187
3257269 = 11 . 314187 - 198788
3257269 = 17 . 198788 - 122127
3257269 = 27 . 122127 - 40160
3257269 = 82 . 40160 - 35851
3257269 = 91 . 35851 - 5172
3257269 = 630 . 5172 - 1091
3257269 = 2986 . 1091 - 457
3257269 = 7128 . 457 - 227
3257269 = 14350 . 227 - 181
3257269 = 17996 . 181 - 7
3257269 = 465325 . 7 - 6
3257269 = 542879 . 6 - 5
3257269 = 651454 . 5 - 1

The end was agonizing, but here we are: the inverse is 3 . 8 . 11 . 17 . 27 . 82 . 91 . 630 . 2986 . 7128 . 14350 . 17996 . 465325 . 542879 . 651454... or 1127070 (mod 3257269).

On a computer, the product could be accumulated modularly, so there is really no need to handle too large numbers.

 

[fresh_42]

One can always break down large numbers via the modulo function and recombine the results with the Chinese remainder theorem. This is not new.