how do I calculate inverse modulo of a number when the modulus is not prime?

Question

I came through Fermat's Little theorem, and it provides a way to calculate inverse modulo of a number when modulus is a prime. but how do I calculate something like this

37inverse mod 900?

Answer 1

Using the Euclidean algorithm and basic algebra we get

$900=24*37+12 \rightarrow 900-24*37=12$

$37=3*12+1 \rightarrow 37-3(900-24*37)=1$

Therefore $73*37-3*900=1$. So the inverse of 37 mod 900 is 73.

Answer 2

Hint: Use Chinese remainder theorem

Answer 3

We describe a way that is analogous to the Fermat Theorem approach. For large moduli $M$ whose rime power factorization is known the method is reasonably efficient. However, the Extended Euclidean Algorithm offers a better path to the inverse.

We first calculate $\varphi(900)$. From the prime power factorization $2^2 3^25^2$ of $900$, this is $(2)(6)(20)=240$. Thus $$37^{240}\equiv 1\pmod{900},$$ and therefore the inverse of $37$ is congruent to $37^{239}$ modulo $900$.

Remark: Instead of using the Euler $\varphi$-function, we can use the Carmichael function $\lambda$. In our case, we have $\lambda(900)=\text{lcm}(2,6,20)=60$ and therefore the inverse of $37$ modulo $900$ is congruent to $37^{59}$ modulo $900$.

Answer 4

Suppose you want to solve:

$$ax\equiv 1\mod b$$

If the two numbers $a$, $b$ are coprime ($\gcd(a,b)=1$), then there exist $u,v$ such that

$$ ua+vb=1 $$

(Obviously, if $b$ is prime, then $a,b$ are always coprime.) You find the numbers $u,v$ using the extended Euclidean algorithm, just as you do when $b$ is prime.

This means that:

\begin{align} ua\equiv1&\mod b \\ x\equiv uax\equiv u&\mod b \end{align}

If $a,b$ are not coprime, then the Extended Euclidean algorithm will give you:

$$ ua+vb=d $$

where $d=\gcd(a,b)$. You can then write $a=jd$ and $b=kd$ to get:

\begin{align} ujd+vkd&=d\\ uj+vk&=1 \end{align}

Use that to solve the following, equivalent, congruence instead, using the same method:

$$ jx\equiv 1\mod k $$