Unknown

106 3. Factors and Zeros

(d) Suppose n is the product of powers of distinct primes p. Show that

4(n)=nn(l-i).

Pb

(e) n = Cdl” 4(d). Verify this for n = 12, 24, 60.

The Mobius function has a role to play in determining the polynomials

Q,, in terms of Pk. Justify the equations

Q6(t) = Pl(t)P’3(t)

P2(t)P3(t)

&g(t) = $f.
3
Generalize to general n. Use the formula obtained to check the degree of
Qn(t), and to obtain QPq(t) when p and q are distinct primes.
E.35. Irreducibility of the Cyclotomic Polynomials. It has already
been observed that the cyclotomic polynomials corresponding to primes
are irreducible. Investigate irreducibility of Qn(t) when n is composite.
E.36. Coefficients of the Cyclotomic Polynomials. If n is equal to a
prime power or twice a prime power, it is easy to check that the coefficients
of Qn(t) are +l or -1. Does this remain true when n is the product of two
primes? Is it true in general?

E.37. Little Fermat Theorem Generalized. The positive integers less
than 24 which are coprime to 24 are 1, 5, 7, 11, 13, 17, 19, 23. Suppose we
take any number coprime with 24, say 7, and multiply each number in this
list by it, reducing the result modulo 24. The list of products in order is
7, 11, 1, 5, 19, 23, 13, 17. Thus, multiplication by 7 simply permutes the
number in the list. To appreciate the significance of this, let us turn to the
general situation.
Let m be a positive integer, k = 4(m) (the function defined in Explo-
ration E.34) and al, as,... , ok be those positive integers less than n which
are coprime with n. Let n be any integer coprime with m. Prove the fol-
lowing:

(i) for each i, there is an index j for which aj E noi (mod m);

(ii) if a, # a,, then na, # na, (mod m);

(iii) for each i, there is an index j for which ai E naj (mod m);

(iv) if the numbers in the set {nal, na2,... , nok} are each replaced by

their remainders upon division by m, we get precisely the numbers

in the set {ai, ~2,... , ok};