# Modular arithmetic

• May 3rd 2011, 02:15 PM
nicola5
Modular arithmetic
Hello!
Can someone please tell me how to calculate the value of the general form
a^(-1) mod b?
A particular example is 97^(-1) mod 4060?
• May 3rd 2011, 02:34 PM
Moo
Euclidean algorithm.
• May 3rd 2011, 02:37 PM
TheEmptySet
Quote:

Originally Posted by nicola5
Hello!
Can someone please tell me how to calculate the value of the general form
a^(-1) mod b?
A particular example is 97^(-1) mod 4060?

You need to use the Euclidean algorithm

$4060=41\cdot 97 +83 \iff 83=4060-41\cdot 97$

$97=1\cdot 83 +14 \iff 14 =97-1\cdot 83$

$83=5\cdot 14+13 \iff 13=83-5\cdot 14$

$14=1\cdot 13+1 \iff 1=14-1\cdot 13$

Now we just need to back substitute to get 1 as a linear combination of 4060 and 97

$1=14-1(83-5\cdot 14)=6\cdot 14-1\cdot 83$

$1=6(97-1\cdot 83)-1\cdot 83=6\cdot 97-7\cdot 83$

$1=6\cdot 97-7\cdot (4060-41\cdot 97)=293\cdot 97-7\cdot 4060$

$1=293\cdot 97-7\cdot 4060 \iff (293)(97) \equiv 1 \mod (4060)$

So 97 is the inverse of 293 mod 4060

Note that this only works if they are coprime