Let $p>3$ be a prime number. Consider the numbers of the form $p - n^2$ where $n = 1 , 2 , 3 , ... , \lfloor\sqrt{p}\rfloor$. Show that there exist two such numbers, $a$ and $b$, that $a | b$.
I tried show that $p - n_{max}^2 | p - 1$. But I’ve found that $p = 107$ is a counter-example.
Edit : $p - n_1^2$ is a and $p - n_2^2$ is b for some $n_1,n_2$
Please give me hints or answers. Thank you!
Let $m:=\lfloor \sqrt{p}\rfloor$. If $p=m^2+1$, then obviously, we have $a\mid b$ if $a:=p-m^2$ and $b:=p-(m-1)^2$. We now suppose that $p-m^2>1$.
We shall prove that, if $a:=p-m^2$, then there exists an integer $k$, where $1\le k<m$, such that $a\mid p-k^2$. First, we note that $p< (m+1)^2-1$; therefore, $p\leq (m+1)^2-2=m^2+2m-1$, so $$a=p-m^2\leq 2m-1\,.\tag{*}$$ Observe that $a\neq m$; otherwise, $p=m^2+a=m^2+m=m(m+1)$, whence $p=2$, but we assume that $p\geq 3$.
Let $X$ be the set of integers $x$ such that $x\equiv -m\pmod{a}$ and $x<m$. Clearly, $X$ is nonempty. Take $k$ to be the largest element of $X$. Then, $k<m$ is given.
Now, if $k\leq 0$, then $k+a\equiv k\equiv -m\pmod{a}$ and $k+a>k$. By maximality of $k$, we must have $k+a\geq m$. Note that $$a\geq m-k\geq m\,.\tag{#}$$ We know that $a\neq m$. That is, $a>m$. Because $k\equiv -m\pmod{a}$ and $k\leq 0$, we must have $k\leq -m$. Thus, by (#), we get $$a\geq m-k \geq 2m\,.$$ This contradicts (*). Hence, $$0<k<m\,.$$ Now, $$p-k^2\equiv p-(-m)^2= p-m^2=a\equiv0\pmod{a}\,,$$ whence $a\mid b$ if $b:=p-k^2$.
For example, when $p=107$, we see that $m=10$ and $a=7$. Thus, if $x$ is an integer such that $x\equiv -m\pmod{a}$, then $x\equiv -10\pmod{7}$, or $x\equiv 4\pmod{7}$. Ergo, $k=4$ works. We can then take $b:=p-k^2=107-16=91=7\cdot 13$, which is divisible by $a=7$.
Remark. This solution does not really use primality of $p$. We can take $p$ to be any positive integer such that $p$ is not of the form $q^2$, $q(q+1)$, and $q(q+2)$ for any integer $q$. For example, if $p=1243=11\cdot 113$, then you can take $m=35$ and $a=18$. Thus, if $x$ is an integer such that $x\equiv -m\pmod{a}$, then $x\equiv -35\pmod{18}$, or $x\equiv 1\pmod{18}$. Ergo, $k=19$ works. We can then take $b:=p-k^2=1243-19^2=882=18\cdot 49$, which is divisible by $a=18$.