Let phi(n) = # of pos. integers < n that's relatively prime to n.

1.) Theorem: phi(n) | n if and only if _______

a.) Show three numbers that will satisfy phi(n) | n.

b.) Fill in the above blank.

c.) Prove this theorem.

-------------

What I know about phi(n)...

n is prime iff phi(n) = n - 1

phi(n) is a multiplicative func.... that is, phi(n) = phi((p_1)^(a_1)*phi((p_2)^(a_2)*...*phi((p_k)^(a_k )

A formula for phi(n) ...

n*(1 - 1/(p_1))*(1 - 1/(p_2))* ... *(1 - 1/(p_k))