2018 AMC 10B Problem 13

Start by testing the first few terms to find a pattern.

1. Test small cases.
- $101 = 101 \times 1$: yes.
- $1001 = 7 \times 11 \times 13$: no.
- $10001 = 73 \times 137$: no.
- $100001 = 11 \times 9091$: no.
- $1000001 = 101 \times 9901$: yes.

So the $1$st and $5$th terms work. It looks like every fourth term works.
2. Why every fourth? Write the terms as $10^k + 1$, so the first term has $k = 2$ (since $100 + 1 = 101$). Look at what $10^k$ is compared to multiples of $101$:
- $10^2 = 100$ is $1$ less than $101$.
- So $10^4 = 100 \times 100$ is $1$ more than a multiple of $101$ (because $100 \times 100 = 10000 = 99 \times 101 + 1$).
- So $10^{k+4} = 10^k \times 10^4$ is $10^k$ times (a multiple of $101$, plus $1$), which is $10^k$ plus a multiple of $101$. Adding a multiple of $101$ does not change whether a number is a multiple of $101$.

So "$10^k + 1$ is a multiple of $101$" repeats every $4$ steps of $k$. It is true for $k = 2$ and false for $k = 3, 4, 5$, as the tests showed.
3. Count. The terms that work are term numbers $1, 5, 9, \ldots$, each one more than a multiple of $4$. The last such number up to $2018$ is $2017 = 4 \times 504 + 1$. The list $1, 5, 9, \ldots, 2017$ has
$$\frac{2017 - 1}{4} + 1 = 504 + 1 = 505$$
numbers.

The answer is $\boxed{\textbf{(C)}\ 505}$.

Whether a power of $10$ plus $1$ is a multiple of a fixed number depends only on the remainder, and remainders of powers repeat in a cycle. Here $100$ is one less than $101$, which makes the cycle length $4$. Once you know the cycle, the problem is counting terms in a list that skips by $4$, and you must be careful at both ends.

With congruences: $10^2 = 100 \equiv -1 \pmod{101}$, which says $100$ leaves remainder $-1$ (one short of a multiple). Then $10^k + 1$ is a multiple of $101$ exactly when $10^k \equiv -1$, which happens for $k = 2, 6, 10, \ldots$. The terms use $k = 2$ up to $k = 2019$, so the good values are $2, 6, \ldots, 2018$, and there are $\frac{2018 - 2}{4} + 1 = 505$ of them.

The $m$-th term is $10^{m+1} + 1$, so the first $2018$ terms are $10^k + 1$ for $k = 2, 3, \dots, 2019$.

Work modulo $101$. Since $10^2 = 100 \equiv -1$, the powers of $10$ cycle with period $4$:
$$10^1 \equiv 10,\quad 10^2 \equiv -1,\quad 10^3 \equiv -10,\quad 10^4 \equiv 1,\quad \dots$$
We need $10^k \equiv -1 \pmod{101}$, which happens exactly when $k \equiv 2 \pmod 4$.

Count the exponents $k \in \{2, \dots, 2019\}$ with $k \equiv 2 \pmod 4$: they are $2, 6, 10, \dots, 2018$, an arithmetic progression with common difference $4$, so there are
$$\frac{2018 - 2}{4} + 1 = 504 + 1 = 505$$
of them.

The answer is $\boxed{\textbf{(C)}\ 505}$.