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

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 _{}