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)}\).