Augustus Acevedo

2022-07-13

System of three linear congruences with three variables
I have the following system
$\left\{\begin{array}{c}5x+20y+11z\equiv 13\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34\right)\\ 16x+9y+13z\equiv 24\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34\right)\\ 14x+15y+15z\equiv 10\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34\right)\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 $\left\{\begin{array}{c}5x+20y+11z\equiv 13\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34\right)\\ -275y-111z\equiv -88\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34\right)\\ -245y-161z\equiv -198\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34\right)\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}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34\right)$. 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}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34\right)$
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}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34\right)$, $y\equiv 15\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34\right)$, $z\equiv 1\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34\right)$
and $x\equiv 5\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34\right)$, $y\equiv 32\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34\right)$, $z\equiv 18\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34\right)$
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}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34\right)$ which is false. Where did I go wrong?

Kroatujon3

Expert

Step 1
By removing the modular arithmetic notations, we can rewrite the system of linear congruence as a system of Diophantine linear equations,
$\left\{\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
$\left\{\begin{array}{l}103x=1205+1020a+2295b-2737c\\ 103y=770+986a+1343b-1887c\\ 103c=-1826-1938a-3485b+4675c\end{array}$
Take modulo 34,
$\left\{\begin{array}{ll}x& \equiv 15+17b-17c\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34\right)\\ y& \equiv 22+17b-17c\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34\right)\\ z& \equiv 10-17b+17c\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34\right)\end{array}$
Step 2
Multiply both sides by 2,
$\left\{\begin{array}{ll}2x& \equiv 30\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34\right)\\ 2y& \equiv 44\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34\right)\\ 2z& \equiv 20\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}34\right)\end{array}\phantom{\rule{1em}{0ex}}\phantom{\rule{thickmathspace}{0ex}}⟹\phantom{\rule{thickmathspace}{0ex}}\phantom{\rule{1em}{0ex}}\left\{\begin{array}{ll}x& \equiv 15\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}17\right)\\ y& \equiv 5\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}17\right)\\ z& \equiv 10\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}17\right)\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:

Do you have a similar question?