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.

Trying to figure out how to solve linear congruence by following through the sample solution to the following problem:

$x \equiv 3$ (mod $7$)
$x \equiv 2$ (mod $5$)
$x \equiv 1$ (mod $3$)

Let:
$n_1$ = 7
$n_2 = 5$
$n_3 = 3$

$N = n_1 \cdot n_2 \cdot n_3 = 105$

$m_1 = \frac{N}{n_1} = 15$

$m_2 = \frac{N}{n_2} = 21$

$m_3 = \frac{N}{n_3} = 35$

$gcd(m_1,n_1)$ = $gcd(15,7) = 1 = 15 \times 1 - 7 \times 2$ so $y_1 = 1$ and $x_1 = 15$
$gcd(m_2,n_2)$ = $gcd(21,5) = 1 = 21 \times 1 - 5 \times 4$ so $y_2 = 1$ and $x_2 = 21$
$gcd(m_3,n_3)$ = $gcd(35,3) = 1 = -35 \times 1 + 3 \times 12$ so $y_3 = -1$ and $x_3 = -35$

I understand up to this point, but the next line I don't get:

So $x = 15 \times 3 + 21 \times 2 - 35 \times 1 \equiv 52$ (mod $105$)

Where is the $\times 3$, $\times 2$, $\times 1$ from? Is it just because there are 3 terms, so it starts from 3 then 2 then 1? And where is the 52 coming from?

share|improve this question
1  
The $3$, $2$, $1$ come from the right-hand sides of the system of congruences you started with. If we had wanted $x\equiv 4\pmod{7}$, $x\equiv 1\pmod{5}$, $x\equiv 0\pmod{3}$, we would use $4$, $1$, $0$ instead of $3$, $2$, $1$. –  André Nicolas Nov 5 '11 at 18:23
    
Ah, of course. I didn't notice. thanks. what about the 52? –  Arvin Nov 5 '11 at 18:59
    
That's easier. $15\times 3+21\times2 +(-35)\times 1=52$. In general we might have gotten a number not in the interval $[0,104]$, and we might want to reduce mod $105$ to get it in that interval, though strictly speaking that is not necessary. –  André Nicolas Nov 5 '11 at 19:05
add comment

3 Answers 3

up vote 1 down vote accepted

Although Bill Cook's answer is completely, 100% correct (and based on the proof of the Chinese Remainder Theorem), one can also work with the congruences successively; we know from the CRT that a solution exists.

Starting from $x\equiv 3\pmod{7}$, this means that $x$ is of the form $x=7k+3$ for some integer $k$. Substituting into the second congruence, we get $$7k+3 \equiv 2\pmod{5}.$$ Since $7\equiv 2\pmod{5}$, and $3\equiv -2\pmod{5}$, this is equivalent to $2k-2\equiv 2\pmod{5}$. Dividing through by $2$ (which we can do since $\gcd(2,5)=1$) we get $k-1\equiv 1\pmod{5}$, or $k\equiv 2\pmod{5}$. That is, $k$ is of the form $k=5r+2$ for some integer $r$.

Plugging this into $x=7k+3$ we have $x=7(5r+2)+3 = 35r + 17$.

Then plugging this into the third (and last) congruence, we get $$35r + 17\equiv 1\pmod{3}.$$ Now, $35\equiv -1\pmod{3}$, $17\equiv -1\pmod{3}$, so this is the same as $-r-1\equiv 1\pmod{3}$, or $r\equiv -2\equiv 1\pmod{3}$. That is, $r$ is of the form $3t+1$. Plugging that into $x$ we get $$x = 35r+17 = 35(3t+1)+17 = 105t + 52,$$ so that means that $x$ is of the form $x=52+105t$ for some integer $t$; that is, $x\equiv 52\pmod{105}$ is the unique solution modulo $3\times5\times 7$.

share|improve this answer
    
Thanks Arturo, I think your answer is a little bit clearer! –  Arvin Nov 6 '11 at 2:04
    
@Arvin: It is, in fact, very close to Bill Dubuque's, only less clever. –  Arturo Magidin Nov 6 '11 at 2:54
add comment

The $3,2,1$ are from the right hand side of your congruences.

We know that $x=3$ is a solution to the first congruence, but this doesn't work as a solution to the next 2 congruences. So Chinese remaindering tells you to compute $(3\cdot 5)^{-1}=15^{-1}$ mod $7$. You find that this is $1$ (since $15(1)+(-2)7=1$). Thus $x=3\cdot 15\cdot 1$ ($=3 \cdot 15 \cdot 15^{-1} = 3 \cdot 1 =3$ (mod $7$) is still a solution of $x \equiv 3 \;\mathrm{mod}\; 7$ since $15\cdot 1 \equiv 1 \;\mathrm{mod}\;7$. What is special about this solution? Well, $x=3\cdot 15\cdot 1$ is also congruent to 0 modulo $3$ and $5$ (that's why we were messing with $(3\cdot 5)^{-1}=15^{-1}$).

Next, $x=2$ solves $x\equiv 2\;\mathrm{mod}\;5$, but again does not solve the other two congruences. So you compute $(3\cdot 7)^{-1}=21^{-1}$ mod $5$. You find that this is $1$ (since $21(1)+5(-4)=1$). Thus $x=2\cdot 21\cdot 1$ is still a solution of $x \equiv 2\;\mathrm{mod}\; 5$ while it is also congruent to 0 modulo $3$ and $7$. So now we've found a solution to the second congruence which doesn't interfere with the first and last congruences.

Finally, $x=1$ solves the third congruence but not the first two. So you compute $(5 \cdot 7)^{-1}=35^{-1}$ mod $3$. You find that this is $-1$ (since $35(-1)+3(12)=1$). Thus $x=1\cdot 35 \cdot (-1)$ is still a solution of $x\equiv 1\;\mathrm{mod}\;3$ while it is congruent to $0$ modulo $5$ and $7$.

So now each congruence has a solution which doesn't interfere with the other congruences. Thus adding the solutions together will solve all 3 at the same time.

Therefore, $x = 3\cdot 15\cdot 1 + 2\cdot 21\cdot 1 + 1\cdot 35 \cdot (-1) = 45+42-35=52$ is a solution to all 3 congruences. Since $105$ ($=3\cdot 5 \cdot 7$) is $0$ modulo $3$, $5$, and $7$, adding multiples of $105$ will still leave us with a solution to all $3$ congruences.

share|improve this answer
1  
@Arvin: It might be worthwhile to view things in a or less identical but more structural way. The number $15$ is congruent to $1$, $0$, $0$ modulo $7$, $5$, $3$; the number $21$ is congruent to $0$, $1$, $0$ modulo $7$, $5$, $3$; the number $-35$ is congruent to $0$, $0$, $1$. (I think $-35$ is kind of silly, would have preferred $70$.) So to get $x\equiv a, b, c$ modulo $7$, $5$, $3$, take the linear combination $a(15)+b(21)+c(-35)$. –  André Nicolas Nov 5 '11 at 19:35
add comment

HINT $\rm\quad y\: :=\: x-2 \equiv 0\pmod 5\ $ so $\rm\: y = 5\:j\:.\ $ Therefore

$\rm\ mod\ 3\!:\ {-}1\equiv y = 5\:j \equiv -j\ \Rightarrow\ j\equiv 1\ \Rightarrow\ y = 5\:(1+3\:k) = 5 + 15\:k$

$\rm\ mod\ 7\!:\ \ \ \ 1 \equiv y = 5 + 15\:k\equiv -2 + k\ \Rightarrow\ k\equiv 3\ \Rightarrow\ y = 5+15\:(3+7\:n) = 50 + 105\:n$

NOTE $\ $ Such exploitation of the "law of small numbers" often yields quicker soltuions than rote application of algorithms (Chinese Remainder Theorem, extended Euclidean algorithm, Hermite-Smith normal forms, etc).

share|improve this answer
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.