Maths Olympiad Prep

Library / Mongolian Mathematical Olympiad /13 of 97

Mongolian Mathematical Olympiad

Number theory Difficulty 5.1 AIME, harder Prove it Mongolia

Find all natural xx such that for every natural nn with 10n+n∣xn+n10^n + n \mid x^n + n?

Solution

Only x=10x = 10.

Assume the contrary and a prime pp that does not divide x−10x - 10. By the Chinese Remainder Theorem we can find a positive integer nn such that
{n≡1(modp−1)n≡−10(modp). \begin{cases} n \equiv 1 \pmod{p-1} \\ n \equiv -10 \pmod{p} \end{cases}.
Then by Fermat's theorem,
10n+n≡10+n≡10−10=0(modp) 10^n + n \equiv 10 + n \equiv 10 - 10 = 0 \pmod{p}
and
xn+n≡x+n≡x−10≢0(modp). x^n + n \equiv x + n \equiv x - 10 \not\equiv 0 \pmod{p}.
It follows that pp divides 10n+n10^n + n but does not divide xn+nx^n + n, x≠10x \neq 10, a contradiction. Hence x=10x = 10 only.

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.