1. ## Congruence system

Hi, i need someone to explain me how to solve the following exercises, please try to be clear because i don't understand too much of it. thanks.

the first problem is how to solve this two exercises:

and the the last one is a system of congruences

2. ## Re: Congruence system

Hey mcolula.

What is covered in your notes?

If you want to get some notes and algorithms, the subjects you need to look at include bi-linear diophantine equations, and the Chinese remainder theorem.

3. ## Re: Congruence system

Hello, mcolula!

If you truly "don't understand too much of it",

$\displaystyle 3x+2 \:\equiv\:4\text{ (mod 7)}$

$\displaystyle \begin{array}{cccccccc}\text{We have:} & 3x &\equiv& 2 & \text{(mod 7)} \\ \text{Multiply by 5:} & 15x & \equiv & 10 & \text{(mod 7)} \\ & x &\equiv & 3 & \text{(mod 7)} \end{array}$

$\displaystyle 2\:\equiv\:5x\text{ (mod 3)}$

$\displaystyle \begin{array}{ccccccc}\text{We have:} & 5x & \equiv & 2 & \text{(mod 3)} \\ & 2x & \equiv & 2 & \text{(mod 3)} \\ & x &\equiv& 1 & \text{(mod 3)} \end{array}$

$\displaystyle x\:\equiv\:9\text{ (mod 7)}$
$\displaystyle x \:\equiv\:6\text{ (mod 2)}$
$\displaystyle x \:\equiv\:5\text{ (mod 5)}$

$\displaystyle \begin{array}{cccccccccccc}x & \equiv & 9 & \text{(mod 7)} & \Rightarrow & x &\equiv & 2 \text{ (mod 7)} & \Rightarrow & x \:=\:2 + 7a \\ x & \equiv & 6 &\text{(mod 2)} & \Rightarrow & x & \equiv & 0\text{ (mod 2)} & \Rightarrow & x\text{ is a multiple of 2.} \\ x & \equiv & 5 & \text{(mod 5)} & \Rightarrow & x &\equiv& 0\text{ (mod 5)} & \Rightarrow & x\text{ is a multiple of 5.} \end{array}$

We have: .$\displaystyle \begin{Bmatrix}x &=& 9+7a & {\color{blue}[1]} \\ x &=& 10b & {\color{blue}[2]}\end{Bmatrix}$

Then: .$\displaystyle 9 + 7a \:=\:10b \quad\Rightarrow\quad a \:=\:\frac{10b-9}{7} \:=\:b-2 + \frac{3b-2}{7}$

Since $\displaystyle a$ is an integer, $\displaystyle 3b-2$ must be a multiple of 7.
. . $\displaystyle 3b-2 \:=\:7c \quad\Rightarrow\quad b \:=\:\frac{7c+2}{3} \:=\:2c + \frac{c+2}{3}$ .[3]

Since $\displaystyle b$ is an integer, $\displaystyle c+2$ must be a multiple of 3.
. . This happens when $\displaystyle c \,=\,3k+1$

Substitute into [3]: .$\displaystyle b \:=\:\frac{7(3k+1)+2}{3} \quad\Rightarrow\quad b \:=\:7k+3$

Substitute into [2]: .$\displaystyle \boxed{x \:=\:10(7k+3)}$