Skip to main content

2018 AMC 10B Problem 13

Problem 13 of 25IntermediateNumber TheoryCounting & Probability

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

Answer choices

Show solution

Solution

The kk-th term is 10k+1+1,10^{k+1} + 1, which 101101 divides iff 10k+1≡−1(mod101).10^{k+1} \equiv -1 \pmod{101}. Notice 102=100≡−1(mod101).10^2 = 100 \equiv -1 \pmod{101}. So 10m≡−110^m \equiv -1 exactly when m≡2(mod4),m \equiv 2 \pmod 4, meaning k+1≡2,k + 1 \equiv 2, that is k≡1(mod4).k \equiv 1 \pmod 4. Among k=1,2,…,2018,k = 1, 2, \ldots, 2018, the values 1,5,…,20171, 5, \ldots, 2017 number 505.505. Thus, C is the correct answer.

More practice

Concepts: modular arithmetic · multiplicative order · counting integers in a range

Problem text and solution from the LIVE past-contest archive. See also the AoPS wiki page for community solutions.