# Find all values of X that satisfy multiple congruences

• October 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?
• October 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?

$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. $x=2\!\!\pmod 5=3\!\!\mod 7$ ...

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

Here is a very primitive solution . . .

Quote:

$\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}$

$\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: . $\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: . $5a + 2 \:=\:7b + 3 \quad\Rightarrow\quad a \:=\:\dfrac{7b+1}{5} \;=\;b + \dfrac{2b + 1}{5}$

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

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

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

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

• October 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.
• October 25th 2010, 04:20 PM
DarK
Quote:

Originally Posted by tonio
$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. $x=2\!\!\pmod 5=3\!\!\mod 7$ ...

Tonio

Could you also solve this using the chinese remainder theorem?
• October 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 $3\cdot 5 +(-2)\cdot 7 =1$ , following the proof of the CRT we define

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

Tonio