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.

  • $\begingroup$ By between, do you mean inclusive/exclusive on the lower and upper bounds? $\endgroup$ – gregkow Jun 15 '14 at 2:51
  • $\begingroup$ 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. $\endgroup$ – user116489 Jun 15 '14 at 2:56
  • $\begingroup$ Hmmm... I have the desire that is exactly opposite to yours: can you tell how you used a computer here? $\endgroup$ – fedja Jun 15 '14 at 4:01
  • $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ Where did the $1 \le k \le 7$ came from? $\endgroup$ – user116489 Jun 15 '14 at 5:41
  • $\begingroup$ $\frac{x^2+y^2}{c}<\frac{2\cdot(2n)^2}{n^2}=8$ $\endgroup$ – 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.

  • $\begingroup$ But how can I found those? Could you add the motivation? $\endgroup$ – user116489 Jun 15 '14 at 2:57
  • $\begingroup$ @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$. $\endgroup$ – user2357112 supports Monica Jun 15 '14 at 3:00
  • $\begingroup$ Ooooops I just re-read the problem and it is not inclusive, $c$ must be greater than $n^2$ $\endgroup$ – user116489 Jun 15 '14 at 3:01
  • $\begingroup$ @user116489: Then you can't do it. For $n=1$, no choice of numbers works. $\endgroup$ – user2357112 supports Monica Jun 15 '14 at 3:02
  • $\begingroup$ Yeah, it mentions that $n \ge 2$ as well. $\endgroup$ – user116489 Jun 15 '14 at 3:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.