The question is:

Determine the smallest multiple of 9 which divided by each of the numbers 2, 5 and 11 leaves a remainder 1.

The answer is 441.

What I did when I tried solving this was to set up 3 different equations:

  • 9n = 1 mod 2
  • 9n = 1 mod 5
  • 9n = 1 mod 11

And solved for each n. I got values of 27, 54 and 108 respectively. I didn't really know where to go from here to get the answer of 441. I think I may be on the wrong path, I'm not really sure. If someone can enlighten me as to why the answer is 441, it will be greatly appreciated.



Since $2$, $5$, and $11$ are relatively prime, your systems is the same as the single equation $$9n\equiv1\mod 110$$ by the Chinese Remainder Theorem. So one approach is to start looking at the multiples of $110$ and add $1$. Real soon you hit $441$, which is the first divisible by $9$.

(Which of course, means $n$ is $441/9$, or $49$.)

You wouldn't even have to guess and check at all, if you compute that $$110\equiv2\mod9$$ then you can see that $$4\cdot110\equiv-1\mod9$$ so $4\cdot110+1$ is your multiple of $9$.

  • $\begingroup$ Ah, I see, thanks. Suppose you decided to take a different approach, such as just solving it. How would you solve for n? $\endgroup$ – Josh M Feb 6 '14 at 2:43
  • $\begingroup$ Ah, thanks a lot :) $\endgroup$ – Josh M Feb 6 '14 at 2:47
  • $\begingroup$ You could solve for $n$ in each of your original three congruences first. But then what would you do? The standard approach would be to use the CRT to merge the three solutions together into a solution mod $441$. Why would we do that when we already had $A\equiv B$ modulo three relatively prime moduli? So we can just skip to the same equation modulo the product. $\endgroup$ – alex.jordan Feb 6 '14 at 2:48
  • $\begingroup$ Or $9n = 1 + 110m \iff 1 + 110m \equiv 0 \pmod 9 \iff 1 + 2m \equiv 0 \pmod 9 \iff 2m \equiv 8 \pmod 9 \iff m = 4$. So $9n = 1 + 110(4) = 441$. $\endgroup$ – steven gregory Jun 28 '16 at 16:21

$5,11\mid 9n\!-\!1\, \Rightarrow\, 55\mid 9n\!-\!1,\ \ $ therefore $\ \ n\equiv \color{#c00}1/9\equiv \color{#c00}{-54}/9\equiv -6\pmod{55}$

${\rm mod}\,\ 2\!:\ 1\equiv 9n\equiv n,\, $ therefore $\ n\,$ is odd $\ \color{#0a0}\Rightarrow\ n \equiv -6 + 55\equiv 49\pmod{2\cdot 55}$

Remark $\ $ We used: $\,\ n\equiv a\pmod m\Leftarrow\!\color{#0a0}\Rightarrow n\equiv a\,$ or $\,n\equiv a+m\pmod {2\cdot m}$


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.