# 2021 JMPSC Invitationals Problems/Problem 11

## Problem

For some $n$, the arithmetic progression $$4,9,14,\ldots,n$$ has exactly $36$ perfect squares. Find the maximum possible value of $n.$

## Solution

First note that the integers in the given arithmetic progression are precisely the integers which leave a remainder of $4$ when divided by $5$.

Suppose a perfect square $m^2$ is in this arithmetic progression. Observe that the remainders when $0^2$, $1^2$, $2^2$, $3^2$, and $4^2$ are divided by $5$ are $0$, $1$, $4$, $4$, and $1$, respectively. Furthermore, for any integer $m$, $$(m+5)^2 = m^2 + 10m + 25 = m^2 + 5(2m + 5),$$ and so $(m+5)^2$ and $m^2$ leave the same remainder when divided by $5$. It follows that the perfect squares in this arithmetic progression are exactly the numbers of the form $(5k+2)^2$ and $(5k+3)^2$, respectively.

Finally, the sequence of such squares is $$(5\cdot 0 + 2)^2, (5\cdot 0 + 3)^2, (5\cdot 1 + 2)^2, (5\cdot 1 + 3)^2,\cdots.$$

In particular, the first and second such squares are associated with $k=1$, the third and fourth are associated with $k=2$, and so on. It follows that the $37^{\text{th}}$ such number, which is associated with $k=18$, is $$(5\cdot 18 + 2)^2 = 92^2 = 9409.$$

Therefore the arithmetic progression must not reach $8464$. This means the desired answer is $\boxed{8459}.$ ~djmathman

## Solution 2

We examine all perfect squares ending in $4$ or $9$ are part of our sequence, so for every cycle of $10$ perfect squares, exactly $4$ are included. This means $9$ cycles are included, which goes until $90^2=8100$. Now, note $92^2=8464$ is not part of our sequence, but is the $37$th perfect square. Therefore, $5$ below this yields $\boxed{8459}$, which is the answer.

~Geometry285

## Solution 3

Since $9-4=5,$ this arithmetic progression has common ratio 5. Thus, all terms in it are in the form $4+5n.$ Taking the modulo 5, all have either $1^2\equiv1\pmod5,2^2\equiv4\pmod5,3^2\equiv4\pmod5,4^2\equiv1\pmod5$ or $5^2\equiv0\pmod5.$ Thus all integers of the form $(2k+2)^2,(2k+3)^2$ are in the arithmetic progression and are perfect squares. This means that the 37 perfect square in the progression is $92^2.$ This also implies that the maximum value of $n$ is $92^2-5=\boxed{8459}$

~pinkpig