Maths Olympiad Prep

Library / /296 of 520

Number theory Difficulty 7.0 National olympiad, round 2 Prove it

For every natural nn let an=20018a_n=20\dots 018 with nn ceros, for example, a1=2018,a3=200018,a7=2000000018a_1=2018, a_3=200018, a_7=2000000018. Prove that there are infinity values of nn such that 20182018 divides ana_n

Solution

1. **Define the sequence ana_n**:
For every natural number nn, let an=20000n zeros18a_n = 20\underbrace{00\cdots0}_{n \text{ zeros}}18. For example, a1=2018a_1 = 2018, a3=200018a_3 = 200018, a7=2000000018a_7 = 2000000018.

2. Claim:
We claim that for each natural n1(mod2018)n \equiv 1 \pmod{2018}, 20182018 divides ana_n. This is sufficient to prove the desired statement since there are infinitely many natural numbers that are congruent to 1(mod2018)1 \pmod{2018}.

3. **Expression for ana_n**:
Note that ana_n can be expressed as:
an=210n+2+18 a_n = 2 \cdot 10^{n+2} + 18

4. Using Fermat's Little Theorem (FLT):
Fermat's Little Theorem states that if pp is a prime and aa is an integer not divisible by pp, then ap11(modp)a^{p-1} \equiv 1 \pmod{p}. Here, we use p=1009p = 1009 (since 2018=2×10092018 = 2 \times 1009).

5. Modulo 1009:
We need to show that 210n+2+180(mod1009)2 \cdot 10^{n+2} + 18 \equiv 0 \pmod{1009} for n1(mod2018)n \equiv 1 \pmod{2018}.

Since n1(mod2018)n \equiv 1 \pmod{2018}, we have:
n=2018k+1for some integer k n = 2018k + 1 \quad \text{for some integer } k

6. Simplify the exponent:
210n+2+182102018k+3+18(mod1009) 2 \cdot 10^{n+2} + 18 \equiv 2 \cdot 10^{2018k + 3} + 18 \pmod{1009}

7. Using FLT:
By Fermat's Little Theorem, 1010081(mod1009)10^{1008} \equiv 1 \pmod{1009}. Therefore:
102018k+3=10(21009k)+3103(mod1009) 10^{2018k + 3} = 10^{(2 \cdot 1009k) + 3} \equiv 10^3 \pmod{1009}

8. **Calculate 103mod100910^3 \mod 1009**:
103=10009(mod1009) 10^3 = 1000 \equiv -9 \pmod{1009}

9. Substitute back:
2102018k+3+182(9)+1818+180(mod1009) 2 \cdot 10^{2018k + 3} + 18 \equiv 2 \cdot (-9) + 18 \equiv -18 + 18 \equiv 0 \pmod{1009}

10. Combine with divisibility by 2:
Since ana_n ends in 8, it is always divisible by 2. Therefore, ana_n is divisible by both 2 and 1009. Since 2 and 1009 are relatively prime, ana_n is divisible by 20182018.

\blacksquare

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.