--------- Problem 3.  
(a) There are two formulae for the Euler's function.
    You must choose the right one.

(b) The smaller the prime divisors of n, the smaller the 
    value of Psi(n).

(c) Let p be a prime divisor of n. Replacing p with 
    some power of p does not change the value of Psi(n),
    from part (a). This gives you the desired sequences.

--------- Problem 4.
(a) Every odd prime divisor of m contributes AT LEAST 
    a factor 2 in the formula for phi(m).
    The even prime 2 contributes only if its appear 
    with a power greater than 1. 

(b) Factor m into primes. Let m=k phi(m), and simplify.

--------- Problem 9.
    Consider the remainder of p modulo 3 and modulo 4 
    separately, then use reciprocity. 

--------- Problem 10.
    How does one characterize quadratic residues in terms
    of a primitive root?

--------- Problem 11.
    What is the set of residues {a, 2a, 3a, ..., (p-1)a}?
    Express the above residue classes in terms of a 
    primitive root, and note that the order of summation 
    is irrelevant.