Maths Olympiad Prep

Library / /314 of 520

Number theory Difficulty 3.3 AMC 10/12 Find the answer

How many of the first 20182018 numbers in the sequence 101,1001,10001,100001,101, 1001, 10001, 100001, \dots are divisible by 101101?

Pick one

Solution

The number 10n+110^n+1 is divisible by 101 if and only if 10n1(mod101)10^n\equiv -1\pmod{101}. We note that (10,102,103,104)(10,1,10,1)(mod101)(10,10^2,10^3,10^4)\equiv (10,-1,-10,1)\pmod{101}, so the powers of 10 are 4-periodic mod 101.
It follows that 10n1(mod101)10^n\equiv -1\pmod{101} if and only if n2(mod4)n\equiv 2\pmod 4.
In the given list, 102+1,103+1,104+1,,102019+110^2+1,10^3+1,10^4+1,\dots,10^{2019}+1, the desired exponents are 2,6,10,,20182,6,10,\dots,2018, and there are 20204=(C) 505\dfrac{2020}{4}=\boxed{\textbf{(C) } 505} numbers in that list.

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.