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:(adsbygoogle = window.adsbygoogle || []).push({});

***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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Procedure to compute a multiplicative inverse

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

**Physics Forums | Science Articles, Homework Help, Discussion**