Problem of the Week 805

True or false?

The fourth annual Konhauser Problemfest was held this past weekend (February 24, 1996) for teams from Macalester, St. Olaf, Carleton, and the University of St. Thomas. Sixteen teams took part; the top two teams (Carleton, Mac) each scored 86 out of a possible 100 points. Past problems are all on my Web page, and this year's problems will be there shortly.

One of this year's problems was:

What is the maximum GCD of n^2 + 1 and (n + 1)^2 + 1 as n varies over the positive integers? It is not too hard by simple algebra do deduce that any divisor of the given integers must divide 5. Or use the following slick approach by Ilan Vardi (Macalester):

Let a = (n+1)^2 + 1, b = n^2 + 1, then simple algebra shows that 2(a+b) - (a-b)^2 = 5. This implies that any number dividing a and b must divide 5. Letting n = 2 proves that the answer is 5.
More interesting is:
If n is a positive integer, then n^5 + 5 and (n+1)^5 + 5 are relatively prime.
- suggested by George Berzsenyi (Quantum)

© Copyright 1996 Stan Wagon. Reproduced with permission.

The Math Forum

2 October 1998