Number theoryDifficulty 7.0National olympiad, round 2Prove it
For every natural n let an=20…018 with n ceros, for example, a1=2018,a3=200018,a7=2000000018. Prove that there are infinity values of n such that 2018 divides an
Solution
1. **Define the sequence an**: For every natural number n, let an=20n zeros00⋯018. For example, a1=2018, a3=200018, a7=2000000018.
2. Claim: We claim that for each natural n≡1(mod2018), 2018 divides an. This is sufficient to prove the desired statement since there are infinitely many natural numbers that are congruent to 1(mod2018).
3. **Expression for an**: Note that an can be expressed as: an=2⋅10n+2+18
4. Using Fermat's Little Theorem (FLT): Fermat's Little Theorem states that if p is a prime and a is an integer not divisible by p, then ap−1≡1(modp). Here, we use p=1009 (since 2018=2×1009).
5. Modulo 1009: We need to show that 2⋅10n+2+18≡0(mod1009) for n≡1(mod2018).
Since n≡1(mod2018), we have: n=2018k+1for some integer k
6. Simplify the exponent: 2⋅10n+2+18≡2⋅102018k+3+18(mod1009)
7. Using FLT: By Fermat's Little Theorem, 101008≡1(mod1009). Therefore: 102018k+3=10(2⋅1009k)+3≡103(mod1009)
10. Combine with divisibility by 2: Since an ends in 8, it is always divisible by 2. Therefore, an is divisible by both 2 and 1009. Since 2 and 1009 are relatively prime, an is divisible by 2018.
■
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.