Olympiad Maths Prep

Library / /2 of 19

Number theory Difficulty 5.1 AIME, harder Prove it Mongolia

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

Solution

Only x=10x = 10.

Assume the contrary and a prime pp that does not divide x10x - 10. By the Chinese Remainder Theorem we can find a positive integer nn such that
{n1(modp1)n10(modp). \begin{cases} n \equiv 1 \pmod{p-1} \\ n \equiv -10 \pmod{p} \end{cases}.
Then by Fermat's theorem,
10n+n10+n1010=0(modp) 10^n + n \equiv 10 + n \equiv 10 - 10 = 0 \pmod{p}
and
xn+nx+nx10≢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, x10x \neq 10, a contradiction. Hence x=10x = 10 only.

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.