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 [itex]x[/itex] satisfying [itex]ax \equiv 1 \pmod m[/itex], where [itex]\gcd(a,m)=1[/itex].

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

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

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

Using the same procedure repeatedly, we obtain a sequence of divisors [itex]q_1, q_2, ..., q_n[/itex] until [itex]r_n=1[/itex]; then the multiplicative inverse of [itex]a[/itex] is the product of all [itex]q_1, q_2, ..., q_n[/itex] (reduce it modulo [itex]m[/itex] 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.