Preselection tests for the full-time training

Question

The positive integer a is relatively prime with 10. Prove that for any positive integer n, there exists a power of a whose last n digits are 0 0_n-1 1.

Accepted Answer

This is equivalent to prove that there exists a positive integer

k

such that

1 0^{n}

divides

a^{k} - 1

.

First solution. Consider the remainders of the division of the

1 0^{n} + 1

powers

a^{1}, a^{2}, \dots, a^{1 0^{n} + 1}

of

a

by

1 0^{n}

. Since there are at most

1 0^{n}

possible remainders, by the pigeonhole principle there exist at least two powers

a^{i}, a^{j}, i < j

, having the same remainder. Therefore

1 0^{n}

divides

a^{j} - a^{i} = a^{i} (a^{j - i} - 1)

. But

1 0^{n}

is relatively prime with

a^{i}

. This proves that

1 0^{n}

divides

a^{j - i} - 1

.

Second solution. Since

a

and

1 0^{n}

are relatively prime, by Euler's theorem

a^{ϕ (1 0^{n})} = a^{4 \cdot 1 0^{n - 1}} \equiv 1 mod 1 0^{n} .

Therefore,

1 0^{n}

divides

a^{4 \cdot 1 0^{n - 1}} - 1

.