Maths Olympiad Prep

Library / /44 of 120

Number theory Difficulty 5.3 AIME, harder Prove it Croatia

Prove that the number whose decimal representation consists of 2187 digits 1 is divisible by 2187.

Solution

Let NN be the number whose decimal representation consists of 2187 digits 1. Then
N=11112187 digits=10218719. N = \underbrace{111\ldots 1}_{2187\ \text{digits}} = \frac{10^{2187} - 1}{9}.

We want to show that 21872187 divides NN.

Note that 2187=372187 = 3^7.

It suffices to show that 373^7 divides NN.

Since N=10218719N = \frac{10^{2187} - 1}{9}, we need to show that 373^7 divides 102187110^{2187} - 1.

Observe that 10k1(mod9)10^k \equiv 1 \pmod{9} for any kk, but we need divisibility by 373^7.

Let us use Euler's theorem:

Since gcd(10,37)=1\gcd(10, 3^7) = 1, Euler's theorem gives 10φ(37)1(mod37)10^{\varphi(3^7)} \equiv 1 \pmod{3^7}, where φ(37)=3736=2187729=1458\varphi(3^7) = 3^7 - 3^6 = 2187 - 729 = 1458.

So 1014581(mod2187)10^{1458} \equiv 1 \pmod{2187}.

But 2187=372187 = 3^7, and 21872187 divides 102187110^{2187} - 1 if and only if the order of 1010 modulo 21872187 divides 21872187.

Alternatively, note that N=10218719N = \frac{10^{2187} - 1}{9}, so NN is an integer, and 373^7 divides NN if and only if 1021871(mod38)10^{2187} \equiv 1 \pmod{3^8}, since N=10218719N = \frac{10^{2187} - 1}{9} and 373^7 divides NN if 1021871(mod38)10^{2187} \equiv 1 \pmod{3^8}.

But actually, since NN is a repunit, and 3k3^k divides 103k110^{3^k} - 1 for k1k \geq 1, we can use induction or known results:

For any k1k \geq 1, 3k3^k divides 103k110^{3^k} - 1.

Proof by induction:

Base case: k=1k = 1, 1031=99910^3 - 1 = 999, which is divisible by 33.

Assume 3k3^k divides 103k110^{3^k} - 1.

Consider 103k+11=(103k)31=(103k1)((103k)2+103k+1)10^{3^{k+1}} - 1 = (10^{3^k})^3 - 1 = (10^{3^k} - 1)((10^{3^k})^2 + 10^{3^k} + 1).

By the induction hypothesis, 3k3^k divides 103k110^{3^k} - 1, so 3k3^k divides 103k+1110^{3^{k+1}} - 1.

But also, 103k1(mod3k)10^{3^k} \equiv 1 \pmod{3^k}, so (103k)2+103k+11+1+1=3(mod3k)(10^{3^k})^2 + 10^{3^k} + 1 \equiv 1 + 1 + 1 = 3 \pmod{3^k}, so 33 divides this factor, so 3k+13^{k+1} divides 103k+1110^{3^{k+1}} - 1.

Therefore, 373^7 divides 10371=102187110^{3^7} - 1 = 10^{2187} - 1.

Thus, 373^7 divides N=10218719N = \frac{10^{2187} - 1}{9}.

Therefore, 21872187 divides the number whose decimal representation consists of 21872187 digits 1.

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.