7.5 MISCELLANEOUS INSTRUCTIVE EXAMPLES 253This concludes our exploration of the equation x^2 + y^2 = p. We have succeeded in
proving that solutions can always be found if p == 1 (mod 4). •
Problems and ExercisesBelow are a wide variety of problems and exercises, arranged in roughly increasing order of diffi
culty.
7.5.9 Example 7.5.1 on page 247 stated that one could
prove that (u + p) - uk k is divisible by p for all values
of k using induction.
(a) Do this induction proof. It is an easy exercise.
(b) Even easier: Think about the factorization of
x" - y". You should know this by heart, but if
not, consult formula 5.2.7 on page 148.
7.5.10 Show that (a+b)P == aP +bP (mod p) for any
primep.
7.5.11 Use the multinomial theorem (Problem 6.1.29
on page 196) to examine
(�y,
a l's
and thus derive yet another combinatorial proof of Fer
mat's little theorem. Explain why this proof is really
equivalent to the one we discussed on page 249.
7.5.12 (Putnam 1983) How many positive integers n
are there such that n is an exact divisor of at least one
of the numbers 1040 , 20^30?
7.5.13 (Russia 1995) Let m and n be positive integers
such that
LCM[m, nj +GCD[m,nj = m+n.
Prove that one of the two numbers is divisible by the
other.
7.5.14 (Russia 1995) Is it possible for the numbers
1, 2, 3,. .. , 100 to be the terms of 12 geometrical pro
gressions?
7.5. 15 (Kiran Kedlaya) Let p be an odd prime and
P(x) a polynomial of degree at most p - 2.
(a) Prove that if P has integer coefficients, then
P(n) +P(n + 1)+···+P(n+p-l) is an in
teger divisible by p for every integer n.
(b) If P(n) +P(n+ 1) + ···+P(n+ p- l) is an in
teger divisible by p for every integer n, must P
have integer coefficients?7.5.16 (lMO 1972) Let m and n be arbitrary non
negative integers. Show thatis an integer.(2m)!(2n)!
m!n!(m +n)!7.5. 17 Find all integer solutions to
x^2 +i +z^2 = 2xyz.
7.5.18 (USAMO 1981) The measure of a given angle
is 1800/ n where n is a positive integer not divisible by
3. Prove that the angle can be trisected by Euclidean
means (straight edge and compasses).
7.5. 19 Show thatare all even if and only if n is a power of 2.
7.5.20 Use Problem 7.5.19 as a starting point for the
more interesting open-ended question: What can you
say about the parity of the numbers in Pascal's trian
gle? Are there patterns? Can you find a formula or
algorithm for the number of odd (or even) numbers in
each row? And can you say anything meaningful about
divisibility modulo m for other values of m?
7.5.21 Show that given p, there exists x such that
d(px) = x and also y such that d(p^2 y) = y.
7.5.22 Show that the number of solutions to d(nx) = n
is I if and only if n equals 1,4, or a prime; is finite if
n is a product of distinct primes; and otherwise is infi
nite.
7.5.23 Show that the sum of the odd divisors of n is
equal to -�(-lr/dd.
�
7.5.24 Let co(n) be the number of distinct primes di
viding n. Show that
� l.u(d) I = 2co(n).
�