Use it to compute inverses mod \((n)\), with just a little cleverness. If \begin{equation*}a^{\phi(n)}\equiv 1\text{ (mod }n)\; ,\end{equation*} then certainly multiplying both sides by \(a^{-1}\) yields \begin{equation*}a^{\phi(n)-1}\equiv a^{-1}\text{ (mod }n)\; .\end{equation*} We can check this using Sage.
Example9.3.1
Let's pick a congruence we wanted to solve earlier, like \begin{equation*}53y\equiv 29\text{ (mod }100)\end{equation*} and try to solve it this way. Instead of all the stuff we did before, we could just multiply both sides by the inverse of 53 in this form.
\begin{equation*}53y\equiv 29\text{ (mod }100)\end{equation*} \begin{equation*}53^{\phi(100)-1}\cdot 53y\equiv 53^{\phi(100)-1}\cdot 29\text{ (mod }100)\end{equation*} Now using Theorem 9.2.3, we get
\begin{equation*}1\cdot y\equiv 29\cdot 53^{\phi(100)-1}\text{ (mod }100)\; .\end{equation*}
One could conceivably do this power by hand using our tricks for powers; using a computer, it would look like the following in Sage.
This answer jells with our previous calculation. Better, I didn't have to solve a different linear congruence in order to solve my original one; I just had to have a way to do multiplication mod \((n)\).
Subsection9.3.2Using Euler's theorem with the CRT
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:
There, we had to calculate many solutions to congruences of the form \begin{equation*}\frac{N}{n_i}x\equiv 1\text{ (mod }n_i)\; .\end{equation*} (This was to get the \(d_i\) numbers.) Our new information means that this inverse is just \begin{equation*}\left(\frac{N}{n_i}\right)^{-1}\equiv \left(\frac{N}{n_i}\right)^{\phi(n_i)-1}\; ,\end{equation*} since we are looking at a congruence modulo \(n_i\).
So the things in the final solution which looked like \begin{equation*}a_i\cdot \frac{N}{n_i}\cdot \left(\frac{N}{n_i}\right)^{-1}\end{equation*} can be thought of as \begin{equation*}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)}\; ,\end{equation*} which is much cooler and simpler! So the answer to the general system is just \begin{equation*}x\equiv \sum_{i=1}^k a_i \Big(\frac{N}{n_i}\Big)^{\phi(n_i)}\text{ (mod }N)\, .\end{equation*}
Example9.3.4
We can do this one step even better. Take a huge system like
\(3x\equiv 7\) (mod \(10\))
\(2x\equiv 5\) (mod \(9\))
\(4x\equiv 1\) (mod \(7\))
Can we find solutions for this using the same mechanism? Yes, and without too much difficulty now.
Since one can solve \(bx\equiv c\) (mod \(n\)) with \begin{equation*}x\equiv b^{\phi(n)-1}\cdot c\; ,\end{equation*} any likely system of congruences with coprime moduli \begin{equation*}b_i x\equiv c_i\text{ (mod }n_i)\end{equation*} where \(N\) is the product of the moduli could be solved by \begin{equation*}x\equiv \sum_{i=1}^k \left(b_i^{\phi(n_i)-1}c_i\right)\left(\frac{N}{n_i}\right)^{\phi(n_i)}\text{ (mod }N)\, .\end{equation*}
Let's use this to solve this system.
Notice that we make as much stuff modulo \(M\) to begin with as possible. Even for bigger numbers, asking Sage to first make things modular is a big help – it takes essentially no time!
Example9.3.5
We can demonstrate this with a much larger example, picking essentially random large primes to compute with. (It's worth trying to time this – recall that we can use %time for this in notebooks, see Sage note 4.2.1.)
