# Thread: Find all values of X that satisfy multiple congruences

1. ## 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?

2. 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

3. Hello, archon!

Here is a very primitive solution . . .

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

4. 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.

5. 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?

6. 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