NTIC Using Euler's Theorem

🔗

Section 9.3 Using Euler's Theorem

🔗

Euler's Theorem has many uses. We will begin with its use in computation.

🔗

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.

xxxxxxxxxx
 
@interact
def _(a=3,n=10):
    a=mod(a,n)
    try:
        b = a^-1
        pretty_print(html(r"$%s^{-1}$ is $%s$ and $%s^{\phi(%s)-1}=%s^{%s-1}$ is also $%s$"%(a, b, a, n, a, euler_phi(n), a^(euler_phi(n)-1))))
    except:
        pretty_print(html("Don't forget to pick an $a$ that actually has an inverse modulo $n$!"))

🔗

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*}$

Now using Theorem 9.2.5, we get

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

xxxxxxxxxx
 
mod(29*53^(euler_phi(100)-1),100)

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

🔗

We can use this to do Chinese Remainder Theorem systems much more easily, as long as we have access to

$\phi\text{.}$

🔗

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

$\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*}$

xxxxxxxxxx
 
a_1,a_2,a_3 = 1,2,3
n_1,n_2,n_3 = 5,6,7
N=n_1*n_2*n_3
print(N)

xxxxxxxxxx
 
print(euler_phi(n_1), euler_phi(n_2), euler_phi(n_3))
print(mod(a_1*(N/n_1)^(euler_phi(n_1)) + a_2*(N/n_2)^(euler_phi(n_2)) + a_3*(N/n_3)^(euler_phi(n_3)),N))

🔗

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

xxxxxxxxxx
 
a_1,a_2,a_3 = 1,2,3
n_1,n_2,n_3 = 5,6,7
N=n_1*n_2*n_3
sum([mod(a*(N/n)^(euler_phi(n)),N) for (a,n) in [(a_1,n_1),(a_2,n_2),(a_3,n_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.

xxxxxxxxxx
 
c_1,c_2,c_3 = 7,5,1
m_1,m_2,m_3 = 10,9,7
M=m_1*m_2*m_3
b_1,b_2,b_3 = mod(3,M),mod(2,M),mod(4,M)
d_1,d_2,d_3 = mod(M/m_1,M),mod(M/m_2,M),mod(M/m_3,M)
print(b_1,b_2,b_3)
print(d_1,d_2,d_3)
print(b_1^(euler_phi(m_1)-1)*c_1*d_1^(euler_phi(m_1)) + b_2^(euler_phi(m_2)-1)*c_2*d_2^(euler_phi(m_2)) + b_3^(euler_phi(m_3)-1)*c_3*d_3^(euler_phi(m_3)))

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.

xxxxxxxxxx
 
c_1,c_2,c_3 = 7,5,1
m_1,m_2,m_3 = random_prime(10000), random_prime(20000), random_prime(30000)
M=m_1*m_2*m_3
b_1,b_2,b_3 = mod(3,M),mod(2,M),mod(4,M)
d_1,d_2,d_3 = mod(M/m_1,M),mod(M/m_2,M),mod(M/m_3,M)
print("Our primes are %s, %s, and %s"%(m_1,m_2,m_3))
print(b_1^(euler_phi(m_1)-1)*c_1*d_1^(euler_phi(m_1)) + b_2^(euler_phi(m_2)-1)*c_2*d_2^(euler_phi(m_2)) + b_3^(euler_phi(m_3)-1)*c_3*d_3^(euler_phi(m_3)))

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.

xxxxxxxxxx
 
c_1,c_2,c_3 = 7,5,1
m_1,m_2,m_3 = random_prime(10^8), random_prime(2*10^8), random_prime(3*10^8)
M=m_1*m_2*m_3
b_1,b_2,b_3 = mod(3,M),mod(2,M),mod(4,M)
d_1,d_2,d_3 = mod(M/m_1,M),mod(M/m_2,M),mod(M/m_3,M)
print("Our primes are %s, %s, and %s"%(m_1,m_2,m_3))
b_1^(euler_phi(m_1)-1)*c_1*d_1^(euler_phi(m_1)) + b_2^(euler_phi(m_2)-1)*c_2*d_2^(euler_phi(m_2)) + b_3^(euler_phi(m_3)-1)*c_3*d_3^(euler_phi(m_3))