1.6. Basic Number Theory and Modular Arithmetic 35Explorations
E.ll. Define the length of the Euclidean algorithm as the number of divi-
sions required to complete it. Find that pair of numbers not exceeding 20
for which the Euclidean algorithm has its greatest length. Answer the same
question replacing 20 by higher numbers. In general, enumerate those pairs
(a, b) of numbers for which the algorithm for the greatest common divisor
is at least as long as the algorithm for any pair (u,v) with 1 5 u 2 a,
llv<b.
E.12. How many solutions (modulo m) are there to the congruence uz E b
(mod m) in general?
E.13. Is it possible to find a polynomial of a single variable n which assumes
a prime value for every integer value of n? One famous attempt turned up
the example n2 - n + 41 which is prime for 0 < n 5 40, but composite
when n = 41. More generally, there are other primes p such as 11 and 17
for which n2 - n + p is prime for 0 5 n 5 p - 1. Checking this is made
easier by the result that, if n2 - n + p is prime for 0 5 n 5 m + 1, then
it is prime for 0 5 n 5 p - 1. This was posed as a problem in the 1987
International Mathematical Olympiad.
Show that, no matter what polynomial p(n) with integer coefficients
is given, there are infinitely many values of the integer n for which the
polynomial assumes a composite value.
However, it is possible to find a polynomial of several variables with in-
teger coefficients for which all the positive values it assumes are primes,
although it will also assume nonpositive values. Such a polynomial is very
complicated. In the next Exploration, you will see how to construct a poly-
nomial all of whose positive values coincide with another well known set.
E.14. Polynomials Whose Positive Values Are Fibonacci Num-
bers. In the year 1202, the eminent mathematician Leonardo of Pisa (Fi-
bonacci) posed in his book, Liber abaci, a famous problem: How many pairs
of rabbits can be produced in a year from a single pair provided that it
begets a new pair at the end of each month from the second month on
and each new pair similarly reproduces? Thus, the original pair survives
without issue through the first two months and produces a second pair at
the end of the second month. At the end of the third month, the older pair
gives rise to a third pair, while at the end of the fourth month, the offspring
of the two oldest pairs bring the number of pairs up to five.
Denote by Fk the number of pairs at the beginning of the kth month (at
the end of the (k - 1)th month). Then for each positive integer n 1 2, the
number Fâ+l of pairs extant during the (n + 1)th month will include the
F,, pairs alive in the previous month plus the offspring of the F,-1 pairs
who were alive two months before. Thus, F,, satisfies the recursion relation
Fl = F2 = 1 F,,+l = F,+F,-1 (n=2,3,4 ,... ).