Let n be an integer greater than or equal to 2. Prove that if k2 + k + n is prime for all integers k such that 0 ≤ k ≤ √(n/3), then k2 + k + n is prime for all integers k such that 0 ≤ k ≤ n - 2.
Solution
First observe that if m is relatively prime to b + 1, b + 2, ... , 2b - 1, 2b, then it is not divisible by any number less than 2b. For if c <= b, then take the largest j ≥ 0 such that 2jc ≤ b. Then 2j+1c lies in the range b + 1, ... , 2b, so it is relatively prime to m. Hence c is also. If we also have that (2b + 1)2 > m, then we can conclude that m must be prime, since if it were composite it would have a factor ≤ √m.
Let n = 3r2 + h, where 0 ≤ h < 6r + 3, so that r is the greatest integer less than or equal to √(n/3). We also take r ≥ 1. That excludes the value n = 2, but for n = 2, the result is vacuous, so nothing is lost.
Assume that n + k(k+1) is prime for k = 0, 1, ... , r. We show by induction that N = n + (r + s)(r + s + 1) is prime for s = 1, 2, ... , n - r - 2. By the observation above, it is sufficient to show that (2r + 2s + 1)2 > N, and that N is relatively prime to all of r + s + 1, r + s + 2, ... , 2r + 2s. We have (2r + 2s + 1)2 = 4r2 + 8rs + 4s2 + 4r + 4s + 1. Since r, s ≥ 1, we have 4s + 1 > s + 2, 4s2 > s2, and 6rs > 3r. Hence (2r + 2s + 1)2 > 4r2 + 2rs + s2 + 7r + s + 2 = 3r2 + 6r + 2 + (r + s)(r + s + 1) >= N.
Now if N has a factor which divides 2r - i with i in the range -2s to r - s - 1, then so does N - (i + 2s + 1)(2r - i) = n + (r - i - s - 1)(r - i - s) which has the form n + s'(s'+1) with s' in the range 0 to r + s - 1. But n + s'(s' + 1) is prime by induction (or absolutely for s = 1), so the only way it can have a factor in common with 2r - i is if it divides 2r - i. But 2r - i ≤ 2r + 2s ≤ 2n - 4 < 2n and n + s'(s' + 1) ≥ n, so if n + s'(s' + 1) has a factor in common with 2r - i, then it equals 2r - i = s + r + 1 + s'. Hence s'2 = s - (n - r - 1) < 0, which is not possible. So we can conclude that N is relatively prime to all of r + s + 1, ... , 2r + 2s and hence prime.
Solutions are also available in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.
© John Scholes
jscholes@kalva.demon.co.uk
13 Nov 1998