Solution April 12, 2007

Problem

Find the number of positive integers $x < 10 2006$ such that $x 2 - x$ is divisible by $102006$ .

Solution

Note that $x^2 - x = (x-1)x\,$ and $10^{2006} = 2^{2006}\cdot5^{2006}\,$ .

Because $x-1\,$ and $x\,$ are coprime, exactly one of them must be divisibly by $2^{2006}\,$ and likewise, one of them must be divisible by $5^{2006}\,$ . This gives us four cases:

$x = 0 \pmod{2^{2006}},\quad x = 0 \pmod{5^{2006}}$

$x = 0 \pmod{2^{2006}},\quad x = 1 \pmod{5^{2006}}$

$x = 1 \pmod{2^{2006}},\quad x = 0 \pmod{5^{2006}}$

$x = 1 \pmod{2^{2006}},\quad x = 1 \pmod{5^{2006}}$

By the Chinese Remainder Theorem (http://en.wikipedia.org/wiki/Chinese_remainder_theorem), each of these cases has a unique solution $0\leq x<10^{2006}$ .

One of these four solutions is $x=0\,$ which is not positive. This leaves us with 3 solutions which satisfy all required conditions.

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