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.
i%7=1   ->  i=1+7n
i%9=2   ->  i=2+9n
i%11=3  ->  i=3+11n

Besides writing out everything:

1,8,15,22...
2,11,20,29...
3,14,25,36...

to find the LCM. Is there a better way to do this?

share|improve this question
1  
Chinese remainder theorem –  MJD Sep 11 '12 at 2:18

2 Answers 2

up vote 4 down vote accepted

In general, you should use the Chinese Remainder Theorem.

However, for these particular numbers, there is a trick! Note that the congruences are equivalent to $2x+5\equiv 0\pmod{7}$, $2x+5\equiv 0\pmod{9}$, and $2x+5\equiv 0\pmod{11}$. So we want $2x+5$ to be divisible by $7$, $9$, and $11$, and therefore by $(7)(9)(11)$, which is $693$. So $2x+5=693$ will work. That gives $x=344$.

Remark: If you are not familiar with congruence notation, look at the sequences of numbers you produced. We will concentrate on the first one, which was $1,8,15,22,\dots$ (there was a mild typo).

Double these, and add $5$. We get $7,21, 35, 49,\dots$, the odd multiples of $7$. Similarly, when you double the numbers in your second sequence, and add $5$, you get the odd multiples of $9$. Similar treatment to the third sequence gets you the odd multiples of $11$. So we want $2x+5$ to be an odd multiple of $(7)(9)(11)$. The smallest positive one is $693$. So now solve $2x+5=693$.

You can also carry through the same argument using the language of remainders. We want $(2x+5)\%7=0$, $(2x+5)\%9=0$, and $(2x+5)\%11=0$.

share|improve this answer
    
I thought OP wanted the least number that satisfied all three relations, which was why I suggested CRT. I agree that it is quite unclear. –  MJD Sep 11 '12 at 2:27
    
@MJD: You are almost certainly right. The question needs to be reworded a bit. –  André Nicolas Sep 11 '12 at 2:29

$\begin{eqnarray}\rm {\bf Hint} &&\rm\qquad\ x &\equiv&\rm n\pmod{2n\!+\!5},\ \ n = 1,2,3\\ \Rightarrow &&\rm\ 2x\!+\!5 &\equiv&\rm 0\pmod{2n\!+\!5},\ \ n = 1,2,3 \end{eqnarray}$

Thus $\rm\:7,9,11\: |\: 2x\!+\!5\:\Rightarrow\: lcm(7,9,11) = 693\:|\:2x\!+\!5.\:$

Therefore $\rm\ mod\ 693\!:\,\ x \,\equiv\, \dfrac{-5}2\,\equiv\, \dfrac{693-5}2 \,\equiv\, 344.$

share|improve this answer

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.