402 Notes on Explorations
Similarly, we can discover that
k(2k - 1) + k = k2 + k2.The number of integers which can be expressed as the sum of its digits
to a given base b is given in the solution to Problem E2925 in Amer. Maih.
Monthly 90 (1983), 401.
(e) Observing that (130)4 = l3 + 33 + 03, (250)~ = 23 + 53 + 03, etc., we
find that, for numbers of base 3k + 1,
k(3k + 1)2 + (2k + 1)(3k + 1) = k3 + (2k + 1)3,and also that
k(3k + 1)2 + (2k + 1)(3k + 1) + 1 = k3 + (2t + 1)3 + 13.(f) (-5x - 3y, -4x - y, -x - 2y, x + 2y, 4x + y, 5x + 3y) and (-4x - 3y,
-5x - 2y, x - y, -x + y, 5x + 2y, 4x + 3y) are two sets of polynomials for
which the sum of the kth powers of the elements of one set are equal to the
corresponding power sums of the second set for 0 _< k 5 5. See the notes
on Exploration E.2 for references.
E.ll. An 1844 result of Gabriel Lame is that the number of steps in the
Euclidean algorithm does not exceed five times the number of digits in the
smaller number. If b is the smaller number in a pair (a, b) for which the
Euclidean algorithm has n steps, it can be shown readily that b is at least as
great as the nth Fibonacci number (see Exploration E.14.) Consult Ross
Honsberger, A theorem of Gabriel Lame, Mathematical Gems II, Dolciani
Mathematical Expositions # 2 (MAA, 1976), 54-57; and H. Grossman,
On the number of divisions in finding a G.C.D., Amer. Math. Monthly 31
(1924), 443.
E.12. The congruence ax E b (mod m) is soluble iff gcd(a, m) divides b, and
there are gcd(a, m) incongruent solutions modulo m. For details, consult
G.H. Hardy & E.M. Wright, An Iniroduction to the Theory ofNumbers, 4th
ed. (Oxford, 1960), Sect. 5.4, 51-52; Sect. 8.1, 94-95; and I. Niven & H.S.
Zuckerman, An Iniroduction to the Theory of Numbers, 2nd ed. (Wiley,
1960, 1966), Sect. 2.3, 31-32.
E.13. Suppose p is odd and f(n) = n2-n+p is prime for 0 5 n 5 @+l.
Then n2 - n + p is prime for 0 < n < p - 1. To see this, assume to the
contrary that n2 - n +p is composite for at least one n not exceeding p- 1.
Let q be the smallest prime that divides any one of the composite values of
f(n) (0 5 n 5 p - 1). Thus q < m = p. (Explain why equality cannot
occur .)
Suppose that u is the smallest nonnegative integer for which qlf(u).
(Explain why f(u) is composite, i.e. not equal to q.) Let q = 2k - 1. Since