# modular arithmetic with different mods

When I am given that $N= 4\mod 5$ and that $N = 0\mod 9$, can I find what the remainder is when $N$ is divided by 45? I know very little of mods and only those that have the same $\mod m$, not of different ones, so I really don't know what to do. Here's a problem if you need to refer to anything...

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

• You can use Chinese Remainder Theorem to find if there is an N that satisfies the first part. To divide a number by $x$, you multiply it by the modular inverse of $x$ in whatever modulus you are using. – XRBtoTheMOON Oct 10 '17 at 15:52
• This is Chinese Remainder theorem territory – Joffan Oct 10 '17 at 15:52
• Using Bezout's identity should help (it is a part of CRT). I got that the remainder is 9. – John Lou Oct 10 '17 at 16:00

So looking at some small numbers $a$ where $a\equiv 4 \bmod 5$:
$a=4,9,14,19,24,29,34,39,44,49,54,59,\ldots$
and some numbers $b$ where $b\equiv 0 \bmod 9$:
$b=0,9,18,27,36,45,54,63,\ldots$
You can see the two matches in the lists of $9$ and $54$, and it shouldn't be surprising that they are $45$ apart, since the remainders of any number with respect to $5$ and $9$ will not be changed by adding a number that is a multiple of both $5$ and $9$. Since $45$ is the least common multiple of $5$ and $9$, this is the modulus to resolve into. And there will be exactly one common value less than this (if there is a solution at all, which there always will be when the original moduluses are coprime). This is fairly easy to satisfy yourself of by trying a few different cases in a small example like this.