Solving $a^2+b^2\equiv 0$ mod $c$ for distinct integers $a,b,c$ constrained between two consecutive squares

Question

Show that for any natural number $n$, between $n^2$ and $(n+1)^2$ one can find three distinct natural numbers $a,b,c$ such that $a^2+b^2$ is divisible by $c$.

A friend and I found a general case that always work with a computer problem, I would like to see a different solution, or a solution that tells the motivation of how to find that general case without a computer.

Answer 1

I would like to see a motivated proof

It looks like it is easier to be divisible by a smaller number, so let $c$ be the least one. The only thing that matters for divisibility of the sum of squares by $c$ is what remainders $a,b$ have modulo $c$, so let $x,y$ be those remainders. Then, since we are squeezed in a narrow window, we have $a=c+x$, $b=c+y$, $c|x^2+y^2$. Now, $c>n^2$ and, certainly, $x,y<2n$, so if $x^2+y^2=kc$, we have $1\le k\le 7$ and it looks like the less $k$ is, the more room we have. Thus, we want $0<x<y$ so that $x^2+y^2>n^2$ and $x^2+y^2+y<(n+1)^2$. Now it is pretty clear where the formulae you mentioned came from: to have more room, we want to have $c$ as much to the left as possible, so let us try $c=n^2+1$. Then the trivial representation $c=x^2+y^2$ with $x=1,y=n$ jumps at you and this choice works. The other extreme would be trying to make the step $y$ as small as possible, i.e., to choose the least $x>\frac n{\sqrt 2}$ and put $y=x+1$. However, the trivial estimate for the "offset" $c-n^2$ will then be of order $3\sqrt 2n$, which is greater than $2n$, so, to make this plan work, we'll need to exercise more care. It is still possible and even gives smaller "range" for really large $n$: you can squeeze $a,b,c$ between $n^2$ and $n^2+qn$ for any $q>\frac 1{\sqrt 2}$ and $n>n_0(q)$, which is pretty much the best one can hope for. Still, this small improvement is hardly worth the cost as far as the original problem is concerned.

Answer 2

This is sort of cheating, since I already saw the answer in your comments, so my ability to reinvent the solution is questionable. That said, here's a hypothetical way to solve it.

We want $a, b, c$ such that

$$a^2 + b^2 \equiv 0 \pmod c$$

This suggests that we pick $c$ to be a sum of squares $d^2+e^2$ and then pick $a$ and $b$ so that

$$a \equiv d \pmod c$$ $$b \equiv e \pmod c$$

Then we have $a^2+b^2 \equiv d^2+e^2 \equiv 0 \pmod c$.

We try some values. With the constraint that $n^2<c<(n+1)^2$, our choices are sort of limited, so it doesn't take too long to hit upon $d=n$, $e=1$. That produces

$$c=n^2+1$$ $$a=n^2+n+1$$ $$b=n^2+2$$

and we're done.