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[/size] (<-- 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.