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!
$\endgroup$ 53 Answers
$\begingroup$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.
$\endgroup$ 8 $\begingroup$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.
$\endgroup$ 9 $\begingroup$$\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.
$\endgroup$
