System of three linear congruences with three variablesI have the following system { 5 x...

Augustus Acevedo

Augustus Acevedo

Answered

2022-07-13

System of three linear congruences with three variables
I have the following system
{ 5 x + 20 y + 11 z 13 ( mod 34 ) 16 x + 9 y + 13 z 24 ( mod 34 ) 14 x + 15 y + 15 z 10 ( mod 34 )
I'm still fairly new to this so I would like anyone so verify my solution.
First, I multiplied equations 2 and 3 by 5, it's a regular transformation because 5 and 34 are coprime. After that, the coefficient next to x in the second equation is 80, and the coefficient of x in the third equation is 70, both of which are a multiply of 5 so we can eliminate them using the first equation.
Hence we get { 5 x + 20 y + 11 z 13 ( mod 34 ) 275 y 111 z 88 ( mod 34 ) 245 y 161 z 198 ( mod 34 )
Next, I multiplied the third equation by 55. It is a regular transformation because 55 and 34 are coprime. The coefficient of y in the third equation is -13475, which is a multiple of -275, so we can eliminate it by multiplying the second equation by -49 and adding it to the third equation.
Now we are left with 3416 6578 ( mod 34 ). If we multiply this equation by -1 and reduce the coefficients (because they are larger than the modulus) we get 16 z 16 ( mod 34 )
We have two typical solutions, z = 1, z = 18.
Now, I proceeded to plug in both values of z gradually and I got two solutions:
x 22 ( mod 34 ), y 15 ( mod 34 ), z 1 ( mod 34 )
and x 5 ( mod 34 ), y 32 ( mod 34 ), z 18 ( mod 34 )
NOTE: I omitted the process of plugging both values of z one by one into the equations because I'm fairly sure I know how to proceed from there. I'm interested in knowing if my method of reducing the system to one equation with one variable is correct or not.
EDIT: After plugging in both sets of solutions, I get that both sets satisfy equations (1) and (2), but in both cases of solutions I get that the third equation ends up being 4 10 ( mod 34 ) which is false. Where did I go wrong?

Answer & Explanation

Kroatujon3

Kroatujon3

Expert

2022-07-14Added 19 answers

Step 1
By removing the modular arithmetic notations, we can rewrite the system of linear congruence as a system of Diophantine linear equations,
{ 5 x + 20 y + 11 z 13 = 34 a 16 x + 9 y + 13 z 24 = 34 b 14 x + 15 y + 15 z 10 = 34 c
Solving this system of equations yields
{ 103 x = 1205 + 1020 a + 2295 b 2737 c 103 y = 770 + 986 a + 1343 b 1887 c 103 c = 1826 1938 a 3485 b + 4675 c
Take modulo 34,
{ x 15 + 17 b 17 c ( mod 34 ) y 22 + 17 b 17 c ( mod 34 ) z 10 17 b + 17 c ( mod 34 )
Step 2
Multiply both sides by 2,
{ 2 x 30 ( mod 34 ) 2 y 44 ( mod 34 ) 2 z 20 ( mod 34 ) { x 15 ( mod 17 ) y 5 ( mod 17 ) z 10 ( mod 17 )
Thus,
- x mod 34 = 15 or 32
- y mod 34 = 5 or 22
- z mod 34 = 10 or 27.
So we got to test for 2 3 = 8 possible triplets of (x,y,z) to substitute into the original system of linear congruence. Trial and error shows that only two such triplets satisfy all three linear congruence: { x mod 34 = 15 y mod 34 = 22 z mod 34 = 10  and  { x mod 34 = 32 y mod 34 = 5 z mod 34 = 27

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get your answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?