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

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.

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