Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

$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|cite|improve this question
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
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|cite|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

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|cite|improve this answer
@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

$ 2x \equiv -1\,$ mod $\,3,5,7\ \begin{array}{r}\iff 3,5,7\mid 2x\!+\!1\!\\ \iff\ \ \ 105\mid 2x\!+\!1\end{array}\!\iff\!$ mod $\,105\!:\ 2x \equiv -1\equiv 104\!\iff\! x\equiv 52\ $

share|cite|improve this answer
@Downvoter fyi: this question was linked to in a comment on a recent question. Perusing it, I noticed this quicker way. I don't understand why this caused you to simultaneously downvote both of my answers here - new and old. In my opinion, improvements should be welcomed. – Bill Dubuque Aug 25 '14 at 13:27

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|cite|improve this answer

Well I used a different approach which involves creating an A.P., creating 3 equations as below and solving. Now that, gives me infinitely many solutions. Rightly so, because 52 is just one number that we can trace, of the many numbers that exist and follow this criteria.

Heads up, this might not be a feasible solution and many will down vote because of that :)

Here it goes:

If $x=3(\mod 7)$

Then, x is a part of the series $10,17,24,31,38,45,52...$

which is an AP with $T1_n=10+(n-1)7$

If $x=2(\mod 5)$

Then, x is a part of the series $7,12,17,22,27...$

which is an AP with $T2_n=7+(n-1)5$

If $x=1(\mod 3)$

Then, x is a part of the series $4,7,10,13,16..$

which is an AP with $T3_n=4+(n-1)3$

All that left is finding common terms between these 3 series. So if we assume, the $n^{th}$ term of the first sequence is similar to the $k^{th}$ term in the second sequence and $p^{th}$ term of the 3rd sequence. Then,

$7n+3=5k+2 \\ \implies 7n+0p-5k=-1 \\ 5k+2=3p+1 \\ \implies 0n-3p+5k=-1 \\ 3p+1=7n+3 \\ \implies 3p-7n+0k=2$

Obviously, this will give infinitely many solutions.

So we use a different approach to solve these equations based on assumption. Looking at the first equation, $k$ has to be greater than $n$ and $49-50=-1$ follows that equation. So, $n=7$ and $k=10$ is one solution.

Using, $k=10$ gives us $p=17$.

So, $T1_7=T2_{10}=T3_{17}$

which is $52$ :)

share|cite|improve this answer

Your Answer


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.