For instance, one has to be just a little clever to use it to compute inverses mod \((n)\).

If \[a^{\phi(n)}\equiv 1\text{ mod }(n)\; ,\] then certainly multiplying both sides by \(a^{-1}\) yields \[a^{\phi(n)-1}\equiv a^{-1}\text{ mod }(n)\; .\] We can check this using Sage.

Let's pick a congruence we wanted to solve earlier, like \[53y\equiv 29\text{ mod }(100)\] and try to solve it with this. Instead of all the stuff we did before, we could just multiply both sides by the inverse of 53 in this form. \[53y\equiv 29\text{ mod }(100)\] \[53^{\phi(100)-1}\cdot 53y\equiv 53^{\phi(100)-1}\cdot 29\text{ mod }(100)\] After the theorem, we get \[1\cdot y\equiv 29\cdot 53^{\phi(100)-1}\text{ mod }(100)\; .\] You could conceivably do this by hand using our tricks for powers; it would look like the following in Sage.

We can use this to do Chinese Remainder Theorem systems much more easily, as long as we have access to \(\phi\).

Remember the algorithm for the CRT, where we tried to solve systems like this:

• \(x\equiv a_1\) mod (\(n_1\))
• \(x\equiv a_2\) mod (\(n_2\))
• \(\cdots\)

There, we had to calculate many solutions to congruences of the form \[\frac{N}{n_i}x\equiv 1\text{ mod }(n_i)\; .\] (This was to get the \(d_i\) numbers.) Our new information means that this inverse is just \[\left(\frac{N}{n_i}\right)^{-1}\equiv \left(\frac{N}{n_i}\right)^{\phi(n_i)-1}\; ,\] since we are looking at a congruence modulo \(n_i\).

So the things in the final solution which looked like \[a_i\cdot \frac{N}{n_i}\cdot \left(\frac{N}{n_i}\right)^{-1}\] can be thought of as \[a_i\cdot \frac{N}{n_i}\cdot \left(\frac{N}{n_i}\right)^{\phi(n_i)-1}=a_i\left(\frac{N}{n_i}\right)^{\phi(n_i)}\; ,\] which is much cooler and simpler! So the answer to the general system is just \[x\equiv \sum_{i=1}^k a_i \Big(\frac{N}{n_i}\Big)^{\phi(n_i)}\, .\]