What's the remainder when this huge number is divided by 45? One of my friends recently gave a mock test of a math exam in which he was asked this horrific question. He asked the same to me and I was totally blank on looking at it. So, it will be a huge help if any of you can solve this.
Here is the question:
A 79 digit long number is made by writing the natural numbers from 1 to 44 in order like  1234567891011121314.....424344. What is the remainder when this number is divided by 45?
Thanks in advance!
Enjoy Solving!
 A: Hint: I'd use the Chinese remainder theorem, which says that the mapping
$${\Bbb Z}_{45} \rightarrow {\Bbb Z}_5\times {\Bbb Z}_9: x\mapsto (x\mod 5, x\mod 9)$$
is a ring isomorphism.
Thus you can separately divide the large number by 5 and by 9. These remainders can then be combined to obtained the remainder modulo 45.
Modulo 5 the situation is simple, just look at the last digit of the number.
Modulo 9, observe that $10 \equiv 1 \mod 9$ and so $10^n\equiv 1 \mod 9$ for each $n\geq 1$. So modulo 9 you just look for the ''Quersumme'' (cross sum).
So you have to find a number $x$ between 0 and 44  such that $x$ is congruent 4 modulo 5 and congruent $Q$ modulo 9, where $Q$ is the cross sum of your number. 
This number is congruent 4 mod 5 and so is one of the following: 4, 9, 14, 19, 24, 29, 34, 39, 44.
A: Let $x$ be your number, let $y$ be its remainder when divided by 45.
Since $x$ and $y$ differ by a multiple of $45$, and each multiple of $45$ is also a multiple of $5$ and a multiple of $9$, $x$ and $y$ have the same remainders when divided by $5$, and also when divided by $9$.
So what you need to do is find the remainders of $x$ when divided by $5$ and by $9$, and then find the number $y$ between $0$ and $44$ that has the same remainders.
A: $\color{#c00}{n \equiv 4}\pmod{5}$ by its unit digit $= 4$, and $\,n\equiv 0\pmod{9}\,$ by casting out nines as below
$$\begin{align} 1 &+\ \  2 + \cdots + 22\\ +\ 44 &+ 43 + \cdots +23\\ \hline 45 &+ 45 + \cdots +45\end{align}\qquad\qquad $$ 
Thus $\ n\bmod 45 = 9 (\color{#c00}n/9  \bmod 5) = 9(\color{#c00}4/4\bmod 5) = 9\,$ by the mod Distributive Law. 
