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

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.

• By between, do you mean inclusive/exclusive on the lower and upper bounds? – gregkow Jun 15 '14 at 2:51
• It must be strict intervals, $n^2 < a,b,c < (n+1)^2$ If it helps, I already found out that $a = n^2+2$ and $b=n^2+n+1$ give $c = n^2+1$. But I haven't found out a way to do it without a computer, I would like to see a motivated proof. – user116489 Jun 15 '14 at 2:56
• Hmmm... I have the desire that is exactly opposite to yours: can you tell how you used a computer here? – fedja Jun 15 '14 at 4:01
• Note that for n=1, then you're looking between 1 and 4 which only has 2 and 3 unless the ends can be included as something to note here. – JB King Jun 15 '14 at 7:10

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.

• Where did the $1 \le k \le 7$ came from? – user116489 Jun 15 '14 at 5:41
• $\frac{x^2+y^2}{c}<\frac{2\cdot(2n)^2}{n^2}=8$ – fedja Jun 15 '14 at 12:19

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.

• But how can I found those? Could you add the motivation? – user116489 Jun 15 '14 at 2:57
• @user116489: Try things? I just tried squaring a few things until I found some numbers that worked. Once I tried squaring $(n+1)^2-1$, it was a pretty easy jump to looking at other multiples of $n$. – user2357112 supports Monica Jun 15 '14 at 3:00
• Ooooops I just re-read the problem and it is not inclusive, $c$ must be greater than $n^2$ – user116489 Jun 15 '14 at 3:01
• @user116489: Then you can't do it. For $n=1$, no choice of numbers works. – user2357112 supports Monica Jun 15 '14 at 3:02
• Yeah, it mentions that $n \ge 2$ as well. – user116489 Jun 15 '14 at 3:05