HINTS FOR CWORK5: --------- 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.