254 CHAPTER 7 NUMBER THEORY
7.5.25 Does there exist an x such that
J.l(x) = J.l(x+ 1) = J.l(x+2) = ... = J.l(x + 1996)?
7.5.26 (Putnam 1983) Let p be an odd prime and let
F(n) := 1 +2n + 3n^2 +. .. + (p - l)nP-^2 •
Prove that if a,b are distinct integers in {O, 1,2, ... ,p
I} then F ( a) and F(b) are not congruent modulo p.
7.5.27 Recall the definition of the inverse image of a
function (page 145). Show that for each n E N,
L J.l(k) =0.
kEtfJ-l(n)
For example, if n = 4, then rl(n) = {5,8, 10, 12} [of
course, you need to verify why there are no other k
such that iP(k) = 4] and
J.l(5) + J.l( 8) + J.l(1O) + J.l(12) = -I +0+ 1 +0 = o.
7.5.28 Does there exist a row of Pascal's Triangle con
taining four distinct elements a, b, c and d such that
b = 2a and d = 2c?
7.5.29 (lMO 1974) Prove that the number
f (2n+^1 ) 23 k
�o 2k+ 1
is not divisible by 5 for any integer n � O.
7.5.30 (Romania 1995) Let f: N\ {O, I} --> N be the
function defined by
f(n) = LCM[I,2, ... ,n].
(a) Prove that for all n, n � 2, there exist n consec
utive numbers for which f is constant.
(b) Find the greatest number of elements of a set of
consecutive integers on which f is strictly in
creasing, and determine all sets for which this
maximum is realized.
7.5.3 1 For a deck containing an even number of cards,
define a "perfect shuffle" as follows: divide the deck
into two equal halves, the top half and the bottom half;
then interleave the cards one by one between the two
halves, starting with the top card of the bottom half,
then the top card of the top half, etc. For example, if
the deck has six cards labeled "123456" from top to
bottom, after a perfect shuffle the order of the cards
will be "415263." Determine the minimum (positive)
number of perfect shuffles needed to restore a 94-card
deck to its original order. Can you generalize this to
decks of arbitrary (even) size?7.5.32 (Iran 1995) Let n > 3 be an odd integer with
prime factorizationIfprove that there is a prime p such that p divides 2m - I,
but does not divide m.Perfect Numbers
Problems 7.5.33-7.5.35 explore some simple ideas
about a topic that has fascinated and perplexed mathe
maticians for at least 2000 years.
7.5.33 Prove the following two facts about the a func
tion:
(a) A positive integer n is prime if and only if
a(n) =n+!.
(b) If a(n) = n + a and aln and a < n, then a must
equal !.
7.5.34 An integer n is called perfect if a(n) = 2n. For
example, 6 is perfect, since 1 + 2 + 3 + 6 = 2 ·6.
(a) Show that if 2 k - 1 is a prime, then 2 k- 1 (2k - 1)
is perfect. This fact was known to the an
cient Greeks, who computed the perfect num
bers 28, 496, 8128.
(b) It was not until the 18 th century that Euler
proved a partial converse to this:
Every even perfect number must be
of the form 2k-1 (2k - I), where 2 k -
I is a prime.
Now you prove it.
7.5.35 What can you say about odd perfect numbers?
(Incidentally, no one has ever found one, or proven that
they do not exist. But that doesn't mean that you can't
say something meaningful about them.)Primitive Roots of Unity and Cyclotomic Poly
nomials
Problems 7.5.36 -7.5.41 explore some fascinating con
nections among polynomials, number theory, and
complex numbers. You may want to read about roots
of unity (page 126) before attempting these problems.
7.5.36 Primitive nth Roots of Unity. The complex
number' is called a primitive nth root of unity if n is