Putnam 2017 A1

This week I worked with Dr. Pragel on the 2017 Putnam A1 problem, and we spent a good amount of time testing values, following patterns, and discussing what happens under squaring and shifting by 5.
It turned into a beautiful example of how a small modular observation unlocks the entire problem.

The Problem

Let be the smallest set of positive integers such that

  2. if then
  3. if then

Which positive integers are not in ?

1. A quick observation

From (2) and (3) we can chain the rules:

If , then , and by (2) this gives .

Hence

so every number in brings along all larger numbers with the same remainder mod 5.

2. Building the first chain

Starting with :

Then again:

Since , we get .

That means we already have a number congruent to 1 mod 5 in .
Because , all large numbers are also in .

3. Mathematical Insight — why any non-multiple of 5 enters

Take any integer with and look at the chain

Each term is the square of the previous one (exactly the pattern allowed by rule (2)).

Modulo 5, there are only four non-zero residues, so these powers eventually repeat.
By Fermat’s Little Theorem, , which means for some we get

Since these powers grow without bound, choose large enough that .
All sufficiently large integers are already in , so .

Now repeatedly apply rule (2) backwards:

Hence every integer not divisible by 5 must lie in .

That’s the formal version of what Dr. Pragel and I explored by testing examples like
— we were empirically tracing the same idea.

4. Describing

Let

We can verify satisfies (1)–(3):

  • if , then and
  • if , then and , so

Thus .

Final Answer

The positive integers not in are

That is, 1 and all multiples of 5.

Written after a fun and insightful whiteboard session with Dr. Pragel — we started by chasing patterns and ended up with a clean modular-theoretic proof.