Solution March 01, 2007

Problem

For all integers $n\geq 1$ we define $x_{n+1}=x_1^2+x_2^2+\cdots +x_n^2$ , where $x 1$ is a positive integer. Find the least $x 1$ such that 2006 divides $x 2006$ .

Solution

Clearly, $x_{n+1} = x_n + x_n^2 = x_n(x_n+1)\,$ .

If $p\,$ divides $x_n\,$ it will also divide $x_m\,$ for all $m\geq n\,$ .

Note that $2006 = 2\cdot 17\cdot 59$ , so we can consider the sequence modulo each of these three primes separately.

Assume that $2006 | x_{2006}\,$ .

Let $p\in\{2,17,59\}\,$ , and let $n\,$ be the smallest index such that $p | x_n\,$ . If $n=1\,$ then $x_1\equiv 0\pmod p$ . Otherwise $x_n = x_{n-1}(x_{n-1}+1)\equiv 0\pmod p$ , i.e. $x_{n-1} \equiv 0\pmod p$ or $x_{n-1} \equiv -1 \pmod p$ . The first possibility is ruled out by our choice of $n\,$ . If $n=2\,$ this implies $x_1\equiv 1\pmod p$ .

Now assume that $n>2\,$ . Then,

$x_{n-1} = x_{n-2}(x_{n-2}+1)\equiv -1 \pmod p\qquad\qquad(1)$

$4x_{n-2}(x_{n-2}+1)-1\equiv -5 \pmod p$

$(2x_{n-2}+1)^2\equiv -5 \pmod p\qquad\qquad(2)$

Now consider each $p\,$ in turn.

If $p=2\,$ , (1) is a contradiction because $x_{n-2}(x_{n-2}+1)\,$ is always even.
If $p=17\,$ we can raise both sides of (2) to the 8-th power and use Fermat's little theorem (http://en.wikipedia.org/wiki/Fermat%27s_little_theorem). The result is $1\equiv -1\pmod{17}$ , a contradiction.
The case $p=59\,$ is very similar. This time, we raise both sides of (2) to the 29-th power and get $1\equiv -1\pmod{59}$ , again a contradiction.

Note: The last two cases show that $-5\,$ is not a quadratic residue (http://en.wikipedia.org/wiki/Quadratic_residue) modulo $17\,$ or $59\,$ .

In summary, we have that $x_1\equiv 0\pmod p$ or $x_1\equiv -1\pmod p$ for $p\in\{2,17,59\}$ . For $p=2\,$ this is no restriction. So we have four cases, which we can solve using the Chinese Remainder Theorem (http://en.wikipedia.org/wiki/Chinese_remainder_theorem)

$x_1\equiv 0\pmod{17}$ and $x_1\equiv 0\pmod{59}$ has solutions $x_1 = 1003k\,$ .
$x_1\equiv -1\pmod{17}$ and $x_1\equiv 0\pmod{59}$ has solutions $x_1 = 1003k+118\,$ .
$x_1\equiv 0\pmod{17}$ and $x_1\equiv -1\pmod{59}$ has solutions $x_1 = 1003k+884\,$ .
$x_1\equiv -1\pmod{17}$ and $x_1\equiv -1\pmod{59}$ has solutions $x_1 = 1003k+1002\,$ .

The smallest positive solution is $x_1=118\,$ . $\square$

Retrieved from "http://www.efnet-math.org/w/Solution_March_01%2C_2007"