Maths Olympiad Prep

Library / /12 of 20

Number theory Difficulty 4.9 AIME Prove it United States

Problem:
Let NN be a positive integer such that NN is divisible by 8181 and the number formed by reversing the digits of NN is also divisible by 8181. Prove that the sum of the digits of NN is divisible by 8181.

Solution

Solution:
We begin with a lemma.
Lemma. For all k0k \geq 0, 10k1+9k(mod81)10^{k} \equiv 1 + 9k \pmod{81}.
Proof. Binomial theorem:
10k=(1+9)k=1k+(k1)1k19+terms divisible by 92. 10^{k} = (1 + 9)^{k} = 1^{k} + \binom{k}{1} 1^{k-1} 9 + \text{terms divisible by } 9^{2}.
We now write NN in terms of its digits as
N=a0+10a1++10nan(a0+90a0)+(a1+91a1)++(an+9nan)a0+a1++an+9(0a0+1a1+2a2++nan)(mod81) \begin{aligned} N &= a_{0} + 10 a_{1} + \cdots + 10^{n} a_{n} \\ &\equiv (a_{0} + 9 \cdot 0 \cdot a_{0}) + (a_{1} + 9 \cdot 1 \cdot a_{1}) + \cdots + (a_{n} + 9 \cdot n \cdot a_{n}) \\ &\equiv a_{0} + a_{1} + \cdots + a_{n} + 9(0 a_{0} + 1 a_{1} + 2 a_{2} + \cdots + n a_{n}) \pmod{81} \end{aligned}
Correspondingly, the number formed by reversing the digits of NN is
an+10an1++10na0a0+a1++an+9(na0+(n1)a1++0an)(mod81). a_{n} + 10 a_{n-1} + \cdots + 10^{n} a_{0} \equiv a_{0} + a_{1} + \cdots + a_{n} + 9(n a_{0} + (n-1) a_{1} + \cdots + 0 a_{n}) \pmod{81}.
If we add these two numbers, we get that 8181 divides
2(a0++an)+9(na0+na1++nan)=(9n+2)(a0++an). 2(a_{0} + \cdots + a_{n}) + 9(n a_{0} + n a_{1} + \cdots + n a_{n}) = (9n + 2)(a_{0} + \cdots + a_{n}).
Since 9n+29n + 2 is not divisible by 33, the conclusion follows.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.