Mastering
the Euler Phi Function:
Exercise 1.
a)
Compute 
and 
b)
Use a counting argument to prove that 
for p prime
and k a positive integer.
Exercise 2.
Our goal now is to prove the following theorem:
Theorem
If 
then 
[1]
a)
Recalling that 
and assuming that 
, prove that the mapping 
defined by
is one-to-one.
b)
Assuming that the “Baby Chinese Remainder Theorem” stated
below is true, prove that 
is onto.
The “Baby” Chinese Remainder Theorem[2]
Let m and n be
integers with gcd(m, n) =1, and let b and c be any
integers. Then the simultaneous
congruences 
and 
have exactly one
solution with 
c)
Use parts a) and b) to explain why you now know that 
implies 
Exercise 3.
Compute 
whenever gcd(m, n) = 1) are said to be multiplicative.