System of three linear congruences with three variables

congruence-relationsdiscrete mathematicsmodular arithmetic

I have the following system

$$
\left\{
\begin{array}{c}
5x+20y+11z \equiv 13 \pmod{34}\\
16x+9y + 13z \equiv 24\pmod{34} \\
14x+15y+15z \equiv 10\pmod{34}
\end{array}
\right.
$$

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 \pmod{34}\\
-275y -111z \equiv -88\pmod{34} \\
-245y-161z \equiv -198\pmod{34}
\end{array}
\right.
$$

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\pmod{34}$. If we multiply this equation by $-1$ and reduce the coefficients (because they are larger than the modulus) we get $$16z \equiv 16\pmod{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\pmod{34}$, $y \equiv 15\pmod{34}$, $z \equiv 1\pmod{34}$

and

$x \equiv 5\pmod{34}$, $y \equiv 32\pmod{34}$, $z \equiv 18\pmod{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.

Thanks!

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\pmod{34}$ which is false. Where did I go wrong?

Best Answer

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

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

Solving this system of equations yields

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

Take modulo $34,$

$$ \begin{cases} x& \equiv 15 + 17b - 17c \pmod{34} \\ y &\equiv 22 + 17b - 17c \pmod{34} \\ z & \equiv 10 - 17b + 17c \pmod{34} \end{cases} $$

Multiply both sides by $2,$

$$ \begin{cases} 2 x & \equiv30 \pmod{34} \\ 2 y & \equiv 44 \pmod{34} \\ 2 z & \equiv 20\pmod{34} \\ \end{cases} \quad \implies \quad \begin{cases} x & \equiv 15 \pmod{17} \\ y & \equiv 5 \pmod{17} \\ z & \equiv 10 \pmod{17} \\ \end{cases} $$

Thus,

  • $ x \bmod {34} = 15$ or $32.$
  • $ y \bmod {34} = 5$ or $22.$
  • $ z \bmod {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:

$$ \boxed{\begin{cases} x \bmod{34} = 15 \\ y \bmod{34} = 22 \\ z \bmod{34} = 10 \\ \end{cases} \quad \text{ and } \quad \begin{cases} x \bmod{34} = 32\\ y \bmod{34} = 5\\ z \bmod{34} = 27 \\ \end{cases}} $$

Related Question