# 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?

• Well, clearly your number is $4\pmod 5$, so you just need to compute it $\pmod 9$. That you can do by summing the digits. Or, more easily, by arguing that you just need to compute $\sum_{n=1}^{44} n \pmod 9$ – lulu Jul 30 at 12:27
• I am sorry @lulu but I didn't get what you're trying to say? – Udit Jethva Jul 30 at 12:29
• @UditJethva: look up en.wikipedia.org/wiki/Chinese_remainder_theorem – Vasya Jul 30 at 12:30
• Where are you confused? If you know the remainder modulo $5,9$ you can use the Chinese remainder theorem to compute it $\pmod {45}$. – lulu Jul 30 at 12:30
• math.stackexchange.com/questions/3152587/… might help a bit, if you know enough math. phi(45)=32 – Roddy MacPhee Jul 30 at 12:31

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.

• I can find out the remainder when it's divided by 5 but how am i going to find it when it's divided by 9? Please help. – Udit Jethva Jul 30 at 12:38
• @UditJethva: do you know divisibility by $9$ rule? Find the sum of digits and divide it by 9, the remainder will be the same when you divide the original number – Vasya Jul 30 at 12:40
• By adding them up. There's only 79 of them, it isn't that hard. You can rearrange them to make it go faster (10 twos sum to 20, for example, and the digits 1 to 9 sum to 45). – Magma Jul 30 at 12:46
• @UditJethva: Modulo $9$, the sum of the digits in the long number is also the sum of the digits in the sum $1+2+3+\dots+44$. There's a formula for that. – awkward Jul 30 at 12:49
• @UditJethva I said the results are the same modulo 9. In your example, note that $4+4$ and $44$ both are $8$, modulo $9$. – awkward Jul 30 at 14:34

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.

• With all due respect to the OP, I doubt that bringing ring isomorphisms into the picture will help them to solve their problem. – TonyK Jul 30 at 12:41
• I would agree: answers shouldn't be more complicated than necessary. – H Huang Jul 30 at 12:44
• Reading the OP's question, I would guess that Udit can't tell a ring isomorphism from a hole in the ground. So it's not much of a hint, is it? – TonyK Jul 30 at 12:52
• Come on you serious mathematicians, think about my solution. Its the easiest one can think of. And this holds for every large number the OP can present. – Wuestenfux Jul 30 at 13:03
• Upvoted. What's the matter with the downvoters? Even if it is too difficult for the OP, it can be useful for someone else! – EpsilonDelta Jul 30 at 13:43

$$\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.