how do I calculate inverse modulo of a number when the modulus is not prime? 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?
 A: 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.
A: 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$. 
A: Hint: Use Chinese remainder theorem
A: 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
$$
A: Though many methods using Euclidean algorithm are mentioned but if you want to calculate $x$ $mod$ $m$ $\forall 1 \leq i \leq m - 1 $, You can simply use the recursion
$$inv[i] = -\lfloor m/i \rfloor * inv[n \% i] $$
The proof is simple,  Consider,
$n = x*(\lfloor m/i \rfloor) + (n \% x)$
$n - (n \% x) = x * (\lfloor m/i \rfloor)$
and take modulo on both sides.
