How to solve congruence equation using table of congruence?

1.4k Views Asked by At

The question first tells us to build the addition table and multiplication table of congruence class modulo 11.

Now we need to solve X:

$$3x + 5 \equiv 2 \pmod{11}$$

I know how to find $3x \equiv 2 \pmod{11}$ (from the multiplication table) which is $x = 8$ but with $+5$ in the equation I don't know how to do it. Do I just sum it $8 + 5 = 13$?

1

There are 1 best solutions below

0
On

One could also find some integer K and multiply the whole equation by it. The integer in particular is one such that $3k\equiv 1\bmod 11 $. You can find this by using the Euclidean Algorithm or just by eyeballing it. Let m be the dividend, n be the divisor, and q be the amount of times n goes into m leaving you with a positive remainder r.

$m\;n\;q\;r$ $\quad$This is the equation $m-(n*q)=r$

$11\;3\;3\;2$ $\quad11-(3*3)=2$

$3\;2\;1\;1$ $\quad3-(2*1)=1$

Using the Extended Euclidean Algorithm you can find such a k that works. Let's start with the second line and work our way up. $1=3-(2*1)$ Substituting this into the first line yields $1=3-(1*(11-3*3))=(3*4)-(11*1)$

From here, we have found our k such that $3k\equiv 1 \bmod 11$

If you multiply your original equation by $k=4$, you get $4(3x+5)\equiv (2*4) \bmod 11$

This simplifies down to $12x+20\equiv 8 \bmod 11$. See that $12\equiv 1\bmod 11$

Thus, $x+20\equiv8\bmod 11$.

Adding $-20$ to both sides yields $x\equiv -12\bmod 11$

Now add $22$ to both sides. Note that $22\equiv 0 \bmod 11$

$x+22\equiv 10 \bmod 11$ which simplifies to $x\equiv 10\bmod 11$

Feel free to comment if you are confused about anything. Note: this is one of my first answers so I am sorry about the quality.