Augustus Acevedo

Answered

2022-07-13

System of three linear congruences with three variables

I have the following system

$\{\begin{array}{c}5x+20y+11z\equiv 13\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)\\ 16x+9y+13z\equiv 24\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)\\ 14x+15y+15z\equiv 10\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)\end{array}$

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 $\{\begin{array}{c}5x+20y+11z\equiv 13\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)\\ -275y-111z\equiv -88\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)\\ -245y-161z\equiv -198\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)\end{array}$

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\equiv -6578\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)$. If we multiply this equation by -1 and reduce the coefficients (because they are larger than the modulus) we get $16z\equiv 16\phantom{\rule{1em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}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\equiv 22\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)$, $y\equiv 15\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)$, $z\equiv 1\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)$

and $x\equiv 5\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)$, $y\equiv 32\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)$, $z\equiv 18\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}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\equiv 10\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)$ which is false. Where did I go wrong?

I have the following system

$\{\begin{array}{c}5x+20y+11z\equiv 13\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)\\ 16x+9y+13z\equiv 24\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)\\ 14x+15y+15z\equiv 10\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)\end{array}$

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 $\{\begin{array}{c}5x+20y+11z\equiv 13\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)\\ -275y-111z\equiv -88\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)\\ -245y-161z\equiv -198\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)\end{array}$

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\equiv -6578\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)$. If we multiply this equation by -1 and reduce the coefficients (because they are larger than the modulus) we get $16z\equiv 16\phantom{\rule{1em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}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\equiv 22\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)$, $y\equiv 15\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)$, $z\equiv 1\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)$

and $x\equiv 5\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)$, $y\equiv 32\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)$, $z\equiv 18\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}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\equiv 10\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)$ which is false. Where did I go wrong?

Answer & Explanation

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,

$\{\begin{array}{l}5x+20y+11z-13=34a\\ 16x+9y+13z-24=34b\\ 14x+15y+15z-10=34c\end{array}$

Solving this system of equations yields

$\{\begin{array}{l}103x=1205+1020a+2295b-2737c\\ 103y=770+986a+1343b-1887c\\ 103c=-1826-1938a-3485b+4675c\end{array}$

Take modulo 34,

$\{\begin{array}{ll}x& \equiv 15+17b-17c\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)\\ y& \equiv 22+17b-17c\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)\\ z& \equiv 10-17b+17c\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)\end{array}$

Step 2

Multiply both sides by 2,

$\{\begin{array}{ll}2x& \equiv 30\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)\\ 2y& \equiv 44\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)\\ 2z& \equiv 20\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)\end{array}\phantom{\rule{1em}{0ex}}\phantom{\rule{thickmathspace}{0ex}}\u27f9\phantom{\rule{thickmathspace}{0ex}}\phantom{\rule{1em}{0ex}}\{\begin{array}{ll}x& \equiv 15\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}17)\\ y& \equiv 5\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}17)\\ z& \equiv 10\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}17)\end{array}$

Thus,

- $xmod34=15$ or 32

- $ymod34=5$ or 22

- $zmod34=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: $\overline{){\displaystyle \{\begin{array}{l}xmod34=15\\ ymod34=22\\ zmod34=10\end{array}\phantom{\rule{1em}{0ex}}\text{and}\phantom{\rule{1em}{0ex}}\{\begin{array}{l}xmod34=32\\ ymod34=5\\ zmod34=27\end{array}}}$

By removing the modular arithmetic notations, we can rewrite the system of linear congruence as a system of Diophantine linear equations,

$\{\begin{array}{l}5x+20y+11z-13=34a\\ 16x+9y+13z-24=34b\\ 14x+15y+15z-10=34c\end{array}$

Solving this system of equations yields

$\{\begin{array}{l}103x=1205+1020a+2295b-2737c\\ 103y=770+986a+1343b-1887c\\ 103c=-1826-1938a-3485b+4675c\end{array}$

Take modulo 34,

$\{\begin{array}{ll}x& \equiv 15+17b-17c\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)\\ y& \equiv 22+17b-17c\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)\\ z& \equiv 10-17b+17c\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)\end{array}$

Step 2

Multiply both sides by 2,

$\{\begin{array}{ll}2x& \equiv 30\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)\\ 2y& \equiv 44\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)\\ 2z& \equiv 20\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34)\end{array}\phantom{\rule{1em}{0ex}}\phantom{\rule{thickmathspace}{0ex}}\u27f9\phantom{\rule{thickmathspace}{0ex}}\phantom{\rule{1em}{0ex}}\{\begin{array}{ll}x& \equiv 15\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}17)\\ y& \equiv 5\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}17)\\ z& \equiv 10\phantom{\rule{0.444em}{0ex}}(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}17)\end{array}$

Thus,

- $xmod34=15$ or 32

- $ymod34=5$ or 22

- $zmod34=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: $\overline{){\displaystyle \{\begin{array}{l}xmod34=15\\ ymod34=22\\ zmod34=10\end{array}\phantom{\rule{1em}{0ex}}\text{and}\phantom{\rule{1em}{0ex}}\{\begin{array}{l}xmod34=32\\ ymod34=5\\ zmod34=27\end{array}}}$

Most Popular Questions