### 42nd Putnam 1981

Problem B3

Prove that infinitely many positive integers n have the property that for any prime p dividing n2 + 3, we can find an integer m such that (1) p divides m2 + 3, and (2) m2 < n.

Solution

I started by finding some small n with the required property. This led to: (1) 52 + 3 = 227, with 7 | 22 + 3, 2 | 12 + 3; (2) 122 + 1 = 723, with 3 | 32 + 3; (3) 232 + 1 = 227 19 with 192 | 42 + 3.

That suggested as the first line of attack looking at special n such as 2a7b. That led nowhere.

My second line of attack was to look for relations of the type (a2 + 3)(b2 + 3) = f(a, b)2 + 3. After some playing around, I obtained (m2 + 3)( (m+1)2 + 3) = M2 + 3, where M = (m2 + m + 3). We are almost there. Any prime factor of M2 + 3 which divides m2 + 3 has the required property since m2 < M. But that is not true for prime factors of (m+1)2 + 3. However, all we have to do is to iterate. We need to split the larger factor:

(m2 + 3)( (m+1)2 + 3)( (m2+m+2)2 + 3) = ( (m2+m+2)2 + (m2+m+2) + 3)2 + 3.

This shows that any n of the form ( (m2+m+2)2 + (m2+m+2) + 3) has the required property.