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 following system of linear congruences in its given form cannot be solved using the Chinese Remainder Theorem. Can you help me transform the system sufficiently such that the Chinese Remainder Theorem can be applied, without actually solving the system?

$$x \equiv 1 \pmod {15}$$ $$2x \equiv 11 \pmod {21}$$ $$4x \equiv −6 \pmod {35}$$

(I can reduce $x \equiv 1 \pmod {15}$ to $x \equiv 1 \pmod 5$ and $x \equiv 1 \pmod 3$.
But I'm not sure how to reduce the other two congruences to end up with mod $3,5$ and $7$?)

Thanks in advance

share|improve this question
1  
Do you know how to simply solve $2x\equiv 11\pmod {21}$ as $x\equiv A\pmod {21}$ for some $A$? –  Thomas Andrews Dec 27 '12 at 22:07
    
gcd(2,21)=1 and 1 divides 11, so there is 1 in-congruent solution modulo 21. x=16 works, so x≡16(mod21) ? –  flamingohats Dec 27 '12 at 22:35
    
I think it is difficult not to see a solution in the effort to transform the system! But there may be more than one solution. –  PAD Dec 27 '12 at 22:39
    
I know that x=16 works, but I am trying to reduce the system to modulo 3,5 and 7 rather than 15,21 and 35 because gcd(15,21,35) is not equal to 1. Is this a correct approach? –  flamingohats Dec 27 '12 at 22:46
    
Yes. That is correct. It works because in both case $x\equiv 1 \ \ (3)$. So, you have consistency. If the same happens on the third equation then you are o.k. I think it works there too because the answer is aganin $16$. –  PAD Dec 27 '12 at 22:52
add comment

2 Answers

$$x \equiv 1 \pmod{15}$$ $$2x \equiv 11 \pmod{21}$$ This means $$x \equiv a \pmod{105}$$ Note that possible values of $a$ consistent with $x \equiv 1 \pmod{15}$ are $\{1,16,31,46,61,76,91\}$. Hence, $2a \in \{2,32,62,92,122,152,182\}$. Now we are given that $2a \equiv 11 \pmod{21}$. Hence, $2a = 32$ is the only possible solution. Hence, $$x \equiv 16 \pmod{105}$$ Further, you have $2x \equiv -3 \pmod{35}$, which is consistent with $x \equiv 16 \pmod{105}$. Hence, we get that $$x \equiv 16 \pmod{105}$$

share|improve this answer
add comment

The general "strategy" is just to transform $$2x\equiv 11\pmod{21}$$ into $$x\equiv 121\pmod{21}=16\pmod{21}$$, where $11$ is $2$'s inverse. From here you can use Chinese reminder theorem.

So solving this we have $$x\equiv 1\pmod{3},x\equiv 2\pmod{7},x\equiv 1\pmod{5}$$Now we use classical algorithm, we have $70*1+21*1+15*2=70+21+30=121\equiv 16\pmod{105}$.

share|improve this answer
    
Not yet. Because $21$ is not prime to $3$. One has to replace $21$ with $7$. –  PAD Dec 27 '12 at 22:48
    
Well, OP should be able to fill in the details if he knows Chinese reminder theorem. –  Bombyx mori Dec 27 '12 at 22:50
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.