5
$\begingroup$

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

It's easy to prove that such three distinct numbers exist, by supposing the contrary and coming to contradiction(i.e."suppose $(n+1)^2-n^2=0$ -->$n=-1$, $-1$ is not a natural number, and so on.."), but how to show divisibility?

(The task is from 1998 St. Petersburg City Mathematical Olympiad)

the problem

$\endgroup$
4
  • 2
    $\begingroup$ Your question is hard to understand as you have written it. Note that strictly between $1$ and $4$ there are not three distinct natural numbers, so what is it you really want? $\endgroup$ Aug 21, 2017 at 11:41
  • $\begingroup$ @MarkBennet..maybe he means that for instance between 1 and 4 some distinct numbers are $1,2,3$ and also $2|(1^2+3^2)=10$..Of course i may be wrong..Indeed the post must be a little more clear. $\endgroup$ Aug 21, 2017 at 12:09
  • $\begingroup$ @MariosGretsas yes, that's exactly what I meant $\endgroup$
    – NiHao92
    Aug 21, 2017 at 12:11
  • $\begingroup$ @NiHao92: Can you please make an edit and clarify that three distinct numbers $a$, $b$ and $c$ exist between $n^2$ and $(n+1)^2$ when $n\ge2$, in agreement with later corrected versions of the book you quote. In future I recommend adding into your question all references to material quoted from copyrighted sources (as well as in this case the original source for the question), to fully protect yourself against the possibility of accusation's of plagiarism or copyright infringement. In this case it would also have saved time in clarifying the meaning of the question. $\endgroup$ Aug 22, 2017 at 13:54

3 Answers 3

8
$\begingroup$

This seems to work with the stricter reading of the problem.

Let $a = n^2 + 2$, $b=n^2+n+1$ and $c=n^2+1$.

If $n \geq 2$ then $n^2 < c < a < b < (n+1)^2$. In particular $a,b,c$ are distinct.

Moreover $$a^2+b^2 = (n^2+2)^2 + (n^2 + n + 1)^2 = (2n(n+1)+5)(n^2+1).$$

So $c | a^2 + b^2$.

I found this by looking at triples $(a,b,c)$ with the required property for small values of $n$ and noticing a pattern. There seem to be lots of other triples which also have the required property; I'm not sure if these can be parameterized nicely.

$\endgroup$
4
$\begingroup$

Surprisingly there seems to be another answer to the stricter reading of the problem.

Let $a=(n^2+n)$, $b=(n^2+n+2)$ and $c=(n^2+1)$

and as with @ARoberts Solution if $n\ge 2$ then $n^2 < c < a < b < (n+1)^2$

we have $a^2+b^2 = (n^2+n)^2 + (n^2 + n + 2)^2 = 2(n^2+1)(n^2+2n+2)$.

So again $c | a^2 + b^2$

$\endgroup$
1
  • $\begingroup$ Perhaps more solutions can be found by splitting $n$ odd and even, or more sub cases e.g. (Mod 4) $4m$, $4m+1$, $4m+2$, $4m+3$. $\endgroup$ Aug 22, 2017 at 13:23
1
$\begingroup$

Since $n^2+2n<(n+1)^2$ and since $n^2$ is included, one obvious answer is

$$\frac{\left(n^2+n \right)^2 +\left(n^2+2n \right)^2 }{n^2}$$

Extended exposition

Since $n^2+2n<(n+1)^2=n^2+2n+1$, let $a=(n^2+n)$, $b=(n^2+2n)$ and $c=n^2$ then $$\frac{a^2+b^2}{c}=\frac{\left(n^2+n \right)^2 +\left(n^2+2n \right)^2 }{n^2}$$

$n^2$ factors out of the numerator and we have $$\frac{a^2+b^2}{c}=\frac{n^2\left(\left(n+1 \right)^2 +\left(n+2 \right)^2\right) }{n^2}=\left(n+1 \right)^2 +\left(n+2 \right)^2$$

Since we now think $n^2$ is not included this simple answer is precluded and left for reference only.

$\endgroup$
5
  • 1
    $\begingroup$ @NiHao92 if $n^2$ is included, the solution become easy, are you sure that $n^2$ included? If this is a question from a book, I think the author waste a portion of a page for a question with only trivial solution... $\endgroup$
    – MAN-MADE
    Aug 21, 2017 at 12:55
  • $\begingroup$ @MANMAID I dunno. Maybe it's a typo. The book is Titu Andreescu and Dorin Andrica- Number Theory. If you find a version where it's not included - means it's a typo lol $\endgroup$
    – NiHao92
    Aug 21, 2017 at 13:41
  • $\begingroup$ @NiHao92 Number theory: Structure, Example and Problems--- is this book? Can you provide the page number? $\endgroup$
    – MAN-MADE
    Aug 21, 2017 at 13:45
  • $\begingroup$ @MANMAID page 20 $\endgroup$
    – NiHao92
    Aug 21, 2017 at 14:11
  • $\begingroup$ see books.google.co.uk/… page 8. the question has been revised here with the criterion $n\ge2$. @MANMAID suspicions are correct I think - that the question is too easy if you include $n$. $\endgroup$ Aug 21, 2017 at 15:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .