8
$\begingroup$

For example,

$4x - 10y \equiv 8\pmod {20}$

$7x + 2y \equiv 5\pmod {20}$

It resembles linear diophantine equations and the Chinese Remainder Theorem, but I don't know how to actually solve it..

$\endgroup$
3
  • 1
    $\begingroup$ Similar techniques to those for solving ordinary systems still apply here. Double the top equation and subtract the second; what do you find out? $\endgroup$
    – John Brevik
    Commented Dec 7, 2017 at 20:54
  • $\begingroup$ When $n$ is squarefree, you can solve the system using Gaussian elimination modulo each prime factor, then compute the overall answer with the Chinese Remainder Theorem. I'm not sure what to do when $n$ isn't squarefree (e.g. 20), though. $\endgroup$
    – user7530
    Commented Dec 7, 2017 at 20:58
  • $\begingroup$ $x -2y = 11$ $mod$ $20$. How do we proceed from here? Do we say $x = 11 + 2y$, substitute that back in and try to work things out from there? On a side note, once we get the solutions, will we have to manually check them? I ask because I'm not sure if all our operations are 'invertible' $\endgroup$
    – John
    Commented Dec 7, 2017 at 21:17

2 Answers 2

Reset to default
8
$\begingroup$

First you can multiply the system by any number that has an inverse, that is $\gcd(x,20)=1$.

So in particular you cannot multiply or divide by $2,4,5,10$ as you would not multiply or divide by $0$ in a normal non-modular system. Well you can do it, but you'll loose equivalence in the way.

For instance here we would like to have $4x-3x$. We notice that $7^{-1}=3\pmod {20}$ so let's multiply the second line by $9$.

$\begin{cases} 4x-10y\equiv 8\pmod{20}\\ 7x+2y\equiv 5\pmod{20}\end{cases}\iff\begin{cases} 4x-10y\equiv 8\pmod{20}\\ 3x+18y\equiv 5\pmod{20}\end{cases}$

Now we can subtract two lines like we do in normal systems

$\begin{cases} 4x-10y\equiv 8\pmod{20}\\ x-28y\equiv 3\pmod{20}\end{cases}\iff\begin{cases} 4x-10y\equiv 8\pmod{20}\\ x\equiv 8y+3\pmod{20}\end{cases}$

We now have $x$ and can report in the first equation

$\begin{cases} 32y+12-10y\equiv 8\pmod{20}\\ x\equiv 8y+3\pmod{20}\end{cases}\iff\begin{cases} 2y\equiv 16\pmod{20}\\ x\equiv 8y+3\pmod{20}\end{cases}$

$2$ is not invertible modulo $20$ but since all coefficients are even, we can divide everything by $2$ including the modulo.

$\begin{cases} y\equiv 8\pmod{10}\\ x\equiv 8y+3\pmod{20}\end{cases}$

Finally report in second equation to get $x$, by introducing a dummy variable $k$ for expressing $y$

$\begin{cases} y\equiv 8\pmod{10}\\ x\equiv 8(10k+8)+3\pmod{20}\equiv 64+3\equiv 7 \pmod{20}\end{cases}$

I have detailed a lot, since this is apparently your first time solving this.

Answering question in comment

$\begin{cases} 2x-6y\equiv 11\pmod{20}\\ 4x+8y\equiv 9\pmod{20}\end{cases}$

Rem: for parity reasons this has no solution, but let's do like we ignore that.

For this one $9$ and $11$ are invertible (and their own inverse), so let's multiply the lines by $9$ and $11$.

You get

$\begin{cases} 2x+14y\equiv 1\pmod{20}\\ 16x+12y\equiv 1\pmod{20}\end{cases}\iff \begin{cases} 2x+14y\equiv 1\pmod{20}\\ 14x-2y\equiv 0\pmod{20}\end{cases}$

Which reduce to $y\equiv 7x\pmod{10}$, and this system has no solution ($2x+14y$ is divisible by $20$).

$\endgroup$
4
  • $\begingroup$ Thank you! How would we do it if none of the coefficients had an inverse? $\endgroup$
    – John
    Commented Dec 7, 2017 at 21:30
  • 1
    $\begingroup$ Then you have to reduce the system by dividing by the $gcd$ of them. For instance we can reduce first equation to $2x-5y\equiv 4\pmod{10}$ and hope for further simplifications. At the end if nothing works, go back to definitions and use $2x-5y=4+10k$ and try to find new equations $\pmod 2$ and $\pmod 5$. $\endgroup$
    – zwim
    Commented Dec 7, 2017 at 21:33
  • $\begingroup$ If we had, say, $2x - 6y = 11$ $mod$ $20$ $4x + 8y = 7$ $mod$ $20$, how would we proceed? $\endgroup$
    – John
    Commented Dec 7, 2017 at 21:40
  • 1
    $\begingroup$ A possible way to deal with this case in edit. But it is obvious that for parity reasons, it has no solutions. $\endgroup$
    – zwim
    Commented Dec 7, 2017 at 22:01
4
$\begingroup$

\begin{eqnarray} 4x - 10y \equiv 8\pmod {20} \\ 7x + 2y \equiv 5\pmod {20} \end{eqnarray}

Method 1 - Take advantage of a unit coefficient (7)

\begin{align} 7x + 2y &\equiv 5\pmod {20} \\ 21x + 6y &\equiv 15\pmod {20} \\ x + 6y &\equiv 15\pmod {20} \\ x &\equiv 14y + 15 \pmod{20} \\ \hline 4(14y + 15) - 10y &\equiv 8\pmod {20} \\ 46y + 60 &\equiv 8 \pmod{20} \\ 6y &\equiv 8 \pmod{20} \\ 3y &\equiv 4 \pmod{10} \\ 21y &\equiv 28 \pmod{10} \\ y &\equiv 8 \pmod{10} \\ y &= 8 + 10 t \\ \hline x &\equiv 14(8 + 10 t) + 15 \pmod{20} \\ x &\equiv 112 + 140t + 15 \pmod{20} \\ x &\equiv 7 \pmod{20} \\ y &\equiv 8 \pmod{10} \\ \end{align}

Method 2 - Convert to prime-power moduli

\begin{eqnarray} 2y &\equiv 0\pmod 4 \\ 3x + 2y &\equiv 1\pmod 4 \\ \hline y &\equiv 0 \pmod 2 \\ \hline 3x &\equiv 1\pmod 4 \\ 9x &\equiv 3\pmod 4 \\ x &\equiv 3 \pmod 4 \end{eqnarray}

\begin{eqnarray} 4x &\equiv 3\pmod 5 \\ 2x + 2y &\equiv 0\pmod 5 \\ \hline -4x &\equiv -3 \pmod 5 \\ x &\equiv 2 \pmod 5 \\ \hline 4 + 2y &\equiv 0\pmod 5 \\ 2 + y &\equiv 0 \pmod 5 \\ y &\equiv 3 \pmod 5 \end{eqnarray}

$\left\{ \begin{array}{c} x \equiv 3 \pmod 4 \\ x \equiv 2 \pmod 5 \\ \end{array} \right\} \implies \left\{ \begin{array}{c} 5x \equiv 15 \pmod{20} \\ -4x \equiv -8 \pmod{20} \\ \end{array} \right\} \implies x \equiv 7 \pmod{20}$

$\left\{ \begin{array}{c} y \equiv 0 \pmod 2\\ y \equiv 3 \pmod 5 \\ \end{array} \right\} \implies \left\{ \begin{array}{c} -5y \equiv 0 \pmod{10} \\ 6y \equiv 18 \pmod{10} \\ \end{array} \right\} \implies y \equiv 8 \pmod{10}$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .