Maths Olympiad Prep

Library / /3 of 520

Number theory Difficulty 6.0 National olympiad Find the answer

Find the number of positive integers x satisfying the following two conditions:
1. x<102006x<10^{2006}
2. x2xx^{2}-x is divisible by 10200610^{2006}

A number or a short expression. Spacing and $ signs are ignored.

Solution

To find the number of positive integers x x satisfying the given conditions, we need to analyze the divisibility condition x2x x^2 - x by 102006 10^{2006} .

1. Condition Analysis:
x2x0(mod102006) x^2 - x \equiv 0 \pmod{10^{2006}}
This implies:
x(x1)0(mod102006) x(x-1) \equiv 0 \pmod{10^{2006}}
Since 102006=22006×52006 10^{2006} = 2^{2006} \times 5^{2006} , we need:
x(x1)0(mod22006)andx(x1)0(mod52006) x(x-1) \equiv 0 \pmod{2^{2006}} \quad \text{and} \quad x(x-1) \equiv 0 \pmod{5^{2006}}

2. **Divisibility by 22006 2^{2006} **:
x(x1)0(mod22006) x(x-1) \equiv 0 \pmod{2^{2006}}
This means either x0(mod22006) x \equiv 0 \pmod{2^{2006}} or x10(mod22006) x-1 \equiv 0 \pmod{2^{2006}} . Therefore:
x0(mod22006)orx1(mod22006) x \equiv 0 \pmod{2^{2006}} \quad \text{or} \quad x \equiv 1 \pmod{2^{2006}}

3. **Divisibility by 52006 5^{2006} **:
x(x1)0(mod52006) x(x-1) \equiv 0 \pmod{5^{2006}}
This means either x0(mod52006) x \equiv 0 \pmod{5^{2006}} or x10(mod52006) x-1 \equiv 0 \pmod{5^{2006}} . Therefore:
x0(mod52006)orx1(mod52006) x \equiv 0 \pmod{5^{2006}} \quad \text{or} \quad x \equiv 1 \pmod{5^{2006}}

4. Combining Conditions Using the Chinese Remainder Theorem:
We need to find the number of solutions x x that satisfy both sets of congruences:
- x0(mod22006) x \equiv 0 \pmod{2^{2006}} and x0(mod52006) x \equiv 0 \pmod{5^{2006}}
- x0(mod22006) x \equiv 0 \pmod{2^{2006}} and x1(mod52006) x \equiv 1 \pmod{5^{2006}}
- x1(mod22006) x \equiv 1 \pmod{2^{2006}} and x0(mod52006) x \equiv 0 \pmod{5^{2006}}

Using the Chinese Remainder Theorem, we can solve these systems of congruences:
- For x0(mod22006) x \equiv 0 \pmod{2^{2006}} and x0(mod52006) x \equiv 0 \pmod{5^{2006}} :
x0(mod102006) x \equiv 0 \pmod{10^{2006}}
This solution is not valid since x x must be positive and less than 102006 10^{2006} .

- For x0(mod22006) x \equiv 0 \pmod{2^{2006}} and x1(mod52006) x \equiv 1 \pmod{5^{2006}} :
There exists exactly one solution 0<x<102006 0 < x < 10^{2006} .

- For x1(mod22006) x \equiv 1 \pmod{2^{2006}} and x0(mod52006) x \equiv 0 \pmod{5^{2006}} :
There exists exactly one solution 0<x<102006 0 < x < 10^{2006} .

5. Counting the Solutions:
Including x=1 x = 1 , we have:
- One solution from x0(mod22006) x \equiv 0 \pmod{2^{2006}} and x1(mod52006) x \equiv 1 \pmod{5^{2006}}
- One solution from x1(mod22006) x \equiv 1 \pmod{2^{2006}} and x0(mod52006) x \equiv 0 \pmod{5^{2006}}
- The solution x=1 x = 1

Therefore, there are a total of 3 solutions.

The final answer is 3 \boxed{3} .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.