Putnam A1, 2017

Putnam 2017, A1) Let $S$ be the smallest set of positive integers that such

a) $2\in S$

b) If $n^2\in S$ , then $n\in S$

c) If $n\in S$ , then $(n+5)^2\in S$

Which positive integers are not in $S$ ?

Although A1 is generally supposed to be one of the easiest problems on the Putnam, I have not been able to solve this problem in the past. Part of the difficulty of the problem arises from the fact that we are not given the answer, and then asked to prove it. Hence, it is easy to miss out on cases, and I for one found it pretty difficult to determine all the cases when I hadn’t looked at the answer (not the proof).

Proof: We prove that all numbers except $1$ and multiples of $5$ belong to $S$ . We know from conditions $b$ and $c$ that $n\in S\implies (n+5)\in S$ . Hence, if we can prove that $2,3,4$ and $6$ belong to $S$ , then we will have proved the assertion.

Proving that $4$ belongs to $S$ is perhaps the only non-trivial step in this problem. Note that we have to find a number of the form $4^{2n}$ to accomplish this, and numbers of the form $4^{2n}$ are $1\pmod 5$ . Hence, as we don’t yet know if there exists a number in $S$ that is $1\pmod 5$ , we do know that there exists a number that is $4\pmod 5$ , which is $(2+5)^2=49$ . On squaring this number, we get $49^2$ , which is obviously $1\pmod 5$ . Now we’re in the game. We just need to find some $4^{2n}$ which is larger than $49^2$ , and then add enough $5$ ‘s until we attain it. Then we take $n$ square roots to get $4$ .