Section 9.3 Using Euler's Theorem
Subsection 9.3.1 Inverses
We can use it to compute inverses modxxxxxxxxxx
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
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.
Now using Theorem 9.2.5, we get
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
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 (mod ) (mod )
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
(mod ) (mod ) (mod )
Can we find solutions for this using the same mechanism? Yes, and without too much difficulty now.
Since one can solve
any likely system of congruences with coprime moduli
where
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
Example 9.3.5.
We can demonstrate this with much larger examples, picking essentially random large primes
(mod ) (mod ) (mod )
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))