# Number Theory Contest Problem

Given that $x, y$ are positive integers with $x(x + 1)\mid y(y + 1)$, but neither $x$ nor $x + 1$ divides either of $y$ or $y + 1$, and $x^2+ y^2$ as small as possible, find $x^2+ y^2$.

I have tried looking at the values, and it seems that neither $x$ or $x+1$ or the $y$'s are prime.

-
I don't see the meaning of $j$? Please correct your post. –  BIS HD Oct 29 '13 at 0:54
Could someone please change $x2+y2$ to a sum of squares? My edit won't be processed. –  Yadnarav3 Oct 29 '13 at 1:03

Yes, we don't want $x$ or $x+1$ to be a prime power. The first candidate is $x=14$. Then $y=20$ works.
Added: Suppose we find consecutive composites integers $x$ and $x+1$ neither of which is a prime power. Let $x=ab$ and $y=cd$, where $a$ and $b$ are relaively prime, as are $c$ and $d$, and none is equal to $1$. Consider the system of congruences $y\equiv 0\pmod{ac}$, $y=\equiv -1\pmod{bd}$. By the Chinese Remainder Theorem, this has a solution. Note that $x$ does not divide $y$, for $b$ divides $y+1$, so is relatively prime to $y$. The other required "non-divisibilities" can be verified in a similar way. But $x(x+1)$ divides $y(y+1)$.
Looking at particular numbers is not guessing, it is finding out what's going on. Nothing serious gets done without preliminary exploration of the territory, sometimes taking years. And I knew that from $2$ consecutive integers that are not prime powers, I could construct suitable $y$ by a Chinese Remainder Theorem argument. Then I would have an upper bound, and the rest in principle would be bounded search. That part I would not have done, it is not interesting. But it so happened that there was a small example. One can produce larger ones, but the question asked for a minimum. –  André Nicolas Oct 29 '13 at 16:26
I have added the sketch of a Chinese Remainder Theorem argument. The $y$ mentioned can be taken to be less than $x(x+1)$. –  André Nicolas Oct 29 '13 at 20:52