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

The question is:

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

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.

Thanks.

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

• Ah, I see, thanks. Suppose you decided to take a different approach, such as just solving it. How would you solve for n? – Josh M Feb 6 '14 at 2:43
• Ah, thanks a lot :) – Josh M Feb 6 '14 at 2:47
• 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. – alex.jordan Feb 6 '14 at 2:48
• 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$. – 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}$