Section 9.3 Using Euler’s Theorem
Euler’s Theorem has many uses, especially theoretical ones we will use throughout. We will begin with its use in some computations we are already familiar with; see
Section 10.5 for some more interesting computational uses.
Subsection 9.3.1 Inverses
We can use it to compute inverses mod \((n)\text{,}\) with just a little cleverness. If
\begin{equation*}
a^{\phi(n)}\equiv 1\text{ (mod }n)\text{,}
\end{equation*}
then certainly multiplying both sides by \(a^{-1}\) yields
\begin{equation*}
a^{\phi(n)-1}\equiv a^{-1}\text{ (mod }n)\text{.}
\end{equation*}
We can check this using Sage.
Example 9.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*}
\begin{equation*}
1\cdot y\equiv 29\cdot 53^{\phi(100)-1}\text{ (mod }100)\text{.}
\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)\text{.}\)
Sage note 9.3.2. Euler phi in Sage.
Notice that Sage has a command to get the Euler phi function, namely euler_phi(n). This doesn’t have the direct connection to the group, but is easier to use than Integers(n).unit_group_order().
Subsection 9.3.2 Using Euler’s theorem with the CRT
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)\text{.}
\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}\text{,}
\end{equation*}
since we are looking at a congruence modulo \(n_i\text{.}\)
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)}\text{,}
\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)\text{.}
\end{equation*}
Sage note 9.3.3. More complex list comprehension.
It’s possible to do the previous work more concisely, no matter how many congruences you have, if you know a little Python and recall from
Sage note 4.6.2 the little something called a ‘
list comprehension 3 ’.
But that’s not necessary for our purposes.
Example 9.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\text{,}
\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)\text{.}
\end{equation*}
Let’s use this to solve this system; we print a few intermediate steps.
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!
Example 9.3.5.
We can demonstrate this with much larger examples, picking essentially random large primes \(m_i\) to compute with.
\(3x\equiv 7\) (mod \(m_1\))
\(2x\equiv 5\) (mod \(m_2\))
\(4x\equiv 1\) (mod \(m_3\))
In the first one, we choose primes in the ten thousands.
It’s worth trying to time this – recall that we can use
%time for this in notebooks, see
Sage note 4.2.1. The second example uses primes in the millions range.
docs.python.org/3/tutorial/datastructures.html#list-comprehensions
