2016 European Girls' Mathematical Olympiad

Lemma. The fourth power of a positive integer $n$ has a divisor in the range $n^2+1,n^2+2,\dots ,n^2+2n$ if and only if at least one of the numbers $2n^2+1$ and $12n^2+9$ is a perfect square. Consequently, a positive integer $n$ is a member of $S$ if and only if $m^2-2n^2=1$ or $m^2-12n^2=9$ for some positive integer $m$.

The former is a Pell equation whose solutions are $(m_1,n_1)=(3,2)$ and $$(m_{k+1},n_{k+1})=(3m_k+4n_k,2m_k+3n_k),k=1,2,3,\dots$$

The other equation is easily transformed into a Pell equation, $m^{\prime 2}-12n^{\prime 2}=1$, by noticing that $m$ and $n$ are both divisible by $3$, say $m=3m^{\prime }$ and $n=3n^{\prime }$. In this case, the solutions are $(m_1,n_1)=(21,6)$ and $$(m_{k+1},n_{k+1})=(7m_k+24n_k,2m_k+7n_k),k=1,2,3,\dots$$ This time iteration shows that $(m_{k+4},n_{k+4})\equiv (m_k,n_k)$. Since $(m_1,n_1)\equiv (0,-1)$, $(m_2,n_2)\equiv (-3,0)$, $(m_3,n_3)\equiv (0,1)$, and $(m_4,n_4)\equiv (3,0)$, it follows that $S$ contains infinitely many integers from each of the residue classes $0$ and $\pm 1$ modulo $7$. Finally, since the $n_k$ from the two sets of formulae exhaust $S$, by the preceding no integer in the residue classes $\pm 3$ modulo $7$ is a member of $S$.

We now turn to the proof of the lemma. Let $n$ be a member of $S$, and let $d=n^2+m$ be a divisor of $n^4$ in the range $n^2+1,n^2+2,\dots ,n^2+2n$, so $1\le m\le 2n$. Consideration of the square of $n^2=d-m$ shows $m^2$ divisible by $d$, so $m^2/d$ is a positive integer. Since $n^2<d<(n+1{)}^2$, it follows that $d$ is not a square; in particular, $m^2/d\ne 1$, so $m^2/d\ge 2$. On the other hand, $1\le m\le 2n$, so $m^2/d=m^2/(n^2+m)\le 4n^2/(n^2+1)<4$. Consequently, $m^2/d=2$ or $m^2/d=3$; that is, $m^2/(n^2+m)=2$ or $m^2/(n^2+m)=3$. In the former case, $2n^2+1=(m-1{)}^2$, and in the latter, $12n^2+9=(2m-3{)}^2$.

Conversely, if $2n^2+1=m^2$ for some positive integer $m$, then $1<m^2<4n^2$, so $1<m<2n$, and $n^4=(n^2+m+1)(n^2-m+1)$, so the first factor is the desired divisor. Similarly, if $12n^2+9=m^2$ for some positive integer $m$, then $m$ is odd, $n\ge 6$, and $n^4=(n^2+m/2+3/2)(n^2-m/2+3/2)$, and again the first factor is the desired divisor.