The Art and Craft of Problem Solving

7.5 MISCELLANEOUS INSTRUCTIVE EXAMPLES 255

the smallest positive integer such that Sn = 1. For ex­

ample, the 4th roots of unity are 1, i, -1, -i, but only

i and -i are primitive 4th roots of unity.

(a) If p is a prime, then there are p -I primitive pth

roots of unity, namely all the pth roots of unity

except for 1:

S, S^2 , S3, ... , Sp-l,

where S = Cis^2 ;.

(b) If S = Cis^2 ::, then Sk is a primitive nth root of

unity if and only if k and n are relatively prime.

Consequently, there are q,(n) primitive nth roots

of unity.

7.5.37 Define <Pn(x) to be the polynomial with lead­
ing coefficient I and degree q,(n) whose roots are
the q,(n) different primitive roots of unity. This

polynomial is known as the nth cyclotomic polyno­

mial. Compute <Pl(X),�(x),,,,,<P 12 (X), and <Pp(x)

and <Pp 2 (for p prime).

7.5.38 Prove that � - 1 = Il <Pd(X) for all positive

din

integers n.

7.5.39 Prove that <Pn (x) = Il (� - 1 )JL(njd).

din

7.5. 40 Prove that for each n E N, the sum of the prim­

itive nth roots of unity is equal to Jl (n ). In other words,

if S := Cis 2 :: ' then

}: Sa = Jl(n).

al.n

l$a<n

7.5.41 Prove that the coefficients of <Pn(x) are integers

for all n. Must the coefficients only be ± I?