# Find all values of X that satisfy multiple congruences

• Oct 22nd 2010, 05:30 AM
archon
Find all values of X that satisfy multiple congruences
The question I'm given is this:

Find all integral values of x such that 2x ≡ 4 (mod 5) and 3x ≡ 2 (mod 7).

I can find all values of x that satisfy each individual congruence, but I'm not sure how to find all values that satisfy both. Could someone lend a hand?
• Oct 22nd 2010, 05:45 AM
tonio
Quote:

Originally Posted by archon
The question I'm given is this:

Find all integral values of x such that 2x ≡ 4 (mod 5) and 3x ≡ 2 (mod 7).

I can find all values of x that satisfy each individual congruence, but I'm not sure how to find all values that satisfy both. Could someone lend a hand?

$\displaystyle 2x=4\!\!\pmod 5\Longleftrightarrow x=2\!\!\pmod 5\,,\,\,3x=2\!\!\pmod 7\Longleftrightarrow x=3\!\!\pmod 7$ , using inverses modulo 5 and modulo 7, resp.

Well, you need all the numbers s.t. $\displaystyle x=2\!\!\pmod 5=3\!\!\mod 7$ ...

Tonio
• Oct 22nd 2010, 08:54 AM
Soroban
Hello, archon!

Here is a very primitive solution . . .

Quote:

$\displaystyle \text{Find all integral values of }x\text{ such that: }\:\begin{array}{ccccc}2x &\equiv& 4 &\text{(mod 5)} \\ 3x &\equiv& 2 & \text{(mod 7)} \end{array}$

$\displaystyle \text{We have: }\:\begin{array}{cccccccccccc} 2x & \equiv & 4 & \text{(mod 5)} & \Rightarrow & x &\equiv& 2 & \text{(mod 5)} \\ 3x & \equiv & 2 & \text{(mod 7)} & \Rightarrow & x &\equiv& 3 & \text{(mod 7)} \end{array}$

This means: .$\displaystyle \begin{array}{ccccccc} x &=& 5a + 2 & \text{for some integer }a & [1] \\ x &=& 7b + 3 & \text{for some integer }b & [2] \end{array}$

We have: .$\displaystyle 5a + 2 \:=\:7b + 3 \quad\Rightarrow\quad a \:=\:\dfrac{7b+1}{5} \;=\;b + \dfrac{2b + 1}{5}$

Since $\displaystyle \,a$ is an integer, $\displaystyle 2b+1$ must be a multiple of 5.

. . Then: .$\displaystyle b \;=\;5k+2\:\text{ for some integer }k.$

Substitute into [2]: .$\displaystyle x \;=\;7(5k+2) + 3 \;=\;35k + 14 + 3$

Therefore: .$\displaystyle x \;=\;35k + 17 \quad\Rightarrow\quad x \:\equiv\:17\text{ (mod 35)}$

• Oct 24th 2010, 06:37 AM
archon
Thanks a lot. I now understand how to solve this problem. I'm going to make sure I know how to solve all problems of this kind by trying them myself now.
• Oct 25th 2010, 04:20 PM
DarK
Quote:

Originally Posted by tonio
$\displaystyle 2x=4\!\!\pmod 5\Longleftrightarrow x=2\!\!\pmod 5\,,\,\,3x=2\!\!\pmod 7\Longleftrightarrow x=3\!\!\pmod 7$ , using inverses modulo 5 and modulo 7, resp.

Well, you need all the numbers s.t. $\displaystyle x=2\!\!\pmod 5=3\!\!\mod 7$ ...

Tonio

Could you also solve this using the chinese remainder theorem?
• Oct 25th 2010, 08:24 PM
tonio
Quote:

Originally Posted by DarK
Could you also solve this using the chinese remainder theorem?

Of course, since 5,7 are coprime: as $\displaystyle 3\cdot 5 +(-2)\cdot 7 =1$ , following the proof of the CRT we define

$\displaystyle x=3\cdot 15+2\cdot (-14)=17$ , and any other solution will equal $\displaystyle 17\!\!\pmod{35=5\cdot 7}$

Tonio