Modular arithmetic

**nicola5** · May 3rd 2011, 01:15 PM

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?

**Moo** · May 3rd 2011, 01:34 PM

Euclidean algorithm.

**TheEmptySet** · May 3rd 2011, 01:37 PM

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

Thread: Modular arithmetic

LinkBack

Thread Tools

Display