Solving a congruence system (which has other solutions)

Question

I am trying to solve this congruence system : $$\begin{cases} 3x+7y\equiv 5[11]\\ 8x+4y\equiv6[11] \end{cases} $$ I multiply first by $8$ and $3$ both equations resp. $$\begin{cases} 24x+56y\equiv40[11]\equiv7 [11]\\ 24x+12y\equiv18[11]\equiv7 [11] \end{cases} $$ We then substract the second equation from the first one. $$44y\equiv0[11],$$ Since $gcd(11,44)=11$, then previous equation is equivalent to : $4y\equiv0[11]$, and then we find that : $$y\equiv0[11],$$ and now I replace it in the following equation : $3x+7\times 0\equiv5[11]$ which is equivalent to : $3x\equiv5[11]$, hence $$x\equiv 9[11]$$ As a result $(9+11k,0+11k')$ with $k,k' \in \mathbb{Z}$ are solutions of the system.

Now my remark is the following : I noticed that also $(0+11k,7+11k')$ with $k,k' \in \mathbb{Z}$ and also $(7+11k,4+11k')$ with $k,k' \in \mathbb{Z}$ are also solutions of the system which I don't understand.

$44y \equiv 0[11]$ does not reduce to $y \equiv 0 [11]$; in fact the first equation is true for any integer $y$. — player3236, Jan 19 '21 at 12:18
In fact, the two equations are negations of each other. $-3\equiv 8\bmod 11$ etc. — Joffan, Jan 19 '21 at 13:04

score 4 · Accepted Answer · answered Jan 19 '21 at 12:25

Since upon elimination the two equations results in $44y \equiv 0 \pmod {11}$ which is true for all integers $y$, the two equations are not independent. As a result, we must express the values of $x$ in terms of $y$ using one of the equations. For example:

$$3x+7y\equiv 5 \pmod {11} \implies 12x + 28y \equiv 20 \pmod {11} \implies x\equiv 9+5y\pmod {11}$$

To verify that $(9+5y,y)$ gives all solutions, we substitute this to the second equation, and we have:

$$8x+4y \equiv 72+44y\equiv 6\pmod {11}$$

so both equations are satisfied. $(9,0), (0,7), (7,4)$ are particular solutions, modulo $11$.

So technically we have $11$ solutions (mod $11$) for : $y=0,1, .... , 10$. — BrianTag, Jan 19 '21 at 12:45

score 1 · Answer 2 · answered Jan 19 '21 at 12:49

A note on reducing $\quad ax\equiv b\pmod m\quad$ and a divider $\quad d$

if $\gcd(m,d)=1$ then you can divide $a,b$ by $d$ and keep the same modulo

e.g. $\quad 6x\equiv 9\pmod{11}\iff 2x\equiv 3\pmod{11}$

if $\gcd(m,d)\neq 1$ and $d$ divides $a,b$ then you can reduce the equation to a lower modulo

e.g. $\quad 6x\equiv 9\pmod{15}\iff 2x\equiv 3\pmod{5}$

In all other cases, try multiplying by $a^{-1}$ or $b^{-1}$ depending on which is relatively prime with the modulo.

e.g. $\, 2^{-1}\equiv 6\pmod{11}\, $ thus $\, 2x\equiv 3\pmod{11}\iff 12x\equiv x\equiv 18\equiv 7\pmod {11}$

In the present case $44y\equiv 0\pmod{11}$, you get in first case for $d=4$ and second case for $d=11$.

$44y\equiv 0\pmod{11}\iff 11y\equiv 0\pmod{11}\iff y\equiv 0\pmod 1\quad$ which is always true for a random integer $y$.

Note that since $44$ is a multiple of $11$ the equation is also simply $0y\equiv 0\pmod{11}$, and this is just some $0=0$ equation, bringing no fuel to the problem (or rather that $y$ is a free variable).

score 0 · Answer 3 · answered Feb 16 '21 at 03:17

The determinant of the matrix $\left[ \begin{array}{cc} 3 & 7 \\ 8 & 4 \end{array} \right]$ is $3 \cdot 4 - 8 \cdot 7 = 1 - 1 = 0 \pmod{11}$

Hence the two equations are linearly dependent.

A little work results in $10(3x+7y) = 30x + 70y = 8x + 4y \pmod{11}$

Hence there is no solution.

Solving a congruence system (which has other solutions)

3 Answers3