1. ## 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?

2. Euclidean algorithm.

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

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

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

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

$\displaystyle 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

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

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

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

$\displaystyle 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