Sample Question 19:

Let $N=123456789101112\dots4344$ be the $79$-digit number that is formed by writing the integers from $1$ to $44$ in order, one after the other. What is the remainder when $N$ is divided by $45$?

$\textbf{(A)}\ 1\qquad\textbf{(B)}\ 4\qquad\textbf{(C)}\ 9\qquad\textbf{(D)}\ 18\qquad\textbf{(E)}\ 44$

---

Answer Keys

Question 19: C

---

Solutions

Question 19
Step 1: Consider the number $N$ modulo $5$ and modulo $9$. The last digit of $N$ makes it clear that $N \equiv 4 \mod 5$.

Step 2: Calculate $N$ modulo $9$ by summing the individual digits of all the integers from $1$ to $44$. This can be written mathematically as $N \equiv 1 + 2 + 3 + \cdots + 44 \mod 9$.

Step 3: Simplify the equation by utilizing the formula for the sum of an arithmetic sequence, which gives us $N \equiv \frac{44 \times 45}{2} \mod 9 = 22 \times 45 \mod 9 \equiv 0 \mod 9$. This tells us that $N$ is divisible by $9$.

Step 4: Let $x$ be the remainder when $N$ is divided by $45$. Based on our previous steps, we know that $x \equiv 0 \mod 9$ and $x \equiv 4 \mod 5$. By applying the Chinese remainder theorem, we find that $x \equiv 5(0) + 9(-1)(4) \mod 45 \equiv -36 \mod 45 \equiv 9 \mod 45$.

So, the answer is $x = 9$, which corresponds to answer choice $\textbf{(C)}$.