Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

Thanks.

share|improve this question
add comment

2 Answers

up vote 6 down vote accepted

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

share|improve this answer
    
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 at 2:43
    
Ah, thanks a lot :) –  Josh M Feb 6 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 at 2:48
add comment

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

share|improve this answer
    
Thanks for this. –  Josh M Feb 6 at 4:14
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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