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

  • 2
    $\begingroup$ 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. $\endgroup$ – XRBtoTheMOON Oct 10 '17 at 15:52
  • 1
    $\begingroup$ This is Chinese Remainder theorem territory $\endgroup$ – Joffan Oct 10 '17 at 15:52
  • $\begingroup$ Using Bezout's identity should help (it is a part of CRT). I got that the remainder is 9. $\endgroup$ – John Lou Oct 10 '17 at 16:00

It might help your intuition to do a couple of these type of problems "by hand", without looking at modular inverses etc, just to get a feel for what is going on, before learning the techniques given in Chinese Remainder theorem discussions.

So looking at some small numbers $a$ where $a\equiv 4 \bmod 5$:


and some numbers $b$ where $b\equiv 0 \bmod 9$:


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.