3.5. Roots of Unity 105(d) Explain how to construct Sicherman dice, two nonstandard cu-
bical dice whose faces are assigned numbers in such a way that
the number of ways of rolling n is the same as for two ordinary
dice.Explorations
E.34. Degree of the Cyclotomic Polynomials. Let 4(n) be the degree
of the polynomial Q,(t). Th is is equal to the number of positive integers a
which are coprime with n, i.e. for which 1 5 a < n and gcd(a, n) = 1.
Let us compute d(24). To find the numbers a between 1 and 24 which
are coprime with 24, we sieve out the multiples of those primes dividing
- We remove 12 multiples of 2 and 8 multiples of 3. However, 4 multiples
of 6 have been removed twice. Consequently, only 12 + 8 - 4 = 16 numbers
have been sieved out and there are 8 remaining: 1, 5, 7, 11, 13, 17, 19, 23.
Thus 4(24) = 8.
If there are three primes dividing n, the situation is more complex. Take
the case n = 60 for instance. Its prime divisors are 2, 3, 5, and in crossing
out multiples of these, we encounter each multiple of 6, 10 and 15 twice
and each multiple of 30 three times. To fix our ideas, assign a weight 1 to
each number to begin with. Every time we cross a number out, its weight
is reduced by 1; every time it is restored, its weight is increased by 1. Our
task is to cross out and restore in such a way that in the end, all multiples
of 2, 3 and 5 have weight 0 and all other numbers have weight 1. Show that
this can be achieved by the following procedures:
cross out all multiples of 2, 3 and 5 in turn
restore all multiples of two of the primes, i.e. of 6, 10, 15, in turn
cross out all multiples of three primes.Thus we start out with 60 numbers, cross out 30+20+ 12, restore 10+6+4
and cross out 2, leaving 16 numbers with weight 1. What are these numbers?
To generalize this, we need the MGbius function p(n):
/J(l) = 1; #u(n) = 0 ‘f 1 n is divisible by any square exceeding 1;
472) = C-1) k i f n is the product of exactly k distinct primes.
Prove the following:
(a) If p is prime, then d(p) = p - 1; +(p”) = pk-‘(p - 1)
(b) 4(n) = x(n/d)p(d) = xdp(n/d) where the sum is taken over all
din din
the divisors of n. Verify this formula for n = 24 and n = 60.(c) If gcd(m,n) = 1, then4(mn) = 4(mM(n>dmn) = f4mMn).