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:



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


[1] Functions satisfying this criteria ( whenever gcd(m, n) = 1) are said to be multiplicative.

[2] Don’t worry…we will prove this theorem and tackle the “Adult” version next lesson!



Back to Block 1 Course Assignments