Solve $15\cdot x=27\pmod{18}$

Question

EXERCISE:

Solve $15\cdot x\equiv 27\pmod{18}$

SOLUTION: We know that $\gcd(15,18)=3$ and $3\setminus 27=3\cdot 9$.

So from http://www.math.niu.edu/~richard/Math420/lin_cong.pdf we can conclude that we have 3 solutions!

Then we have that $15\cdot x\equiv 27\pmod{18}\implies 5\cdot x\equiv 9\pmod{6}$

So, from now and then I can't understand how to proceed!

The book continue with this: "We have a unique solution of $5\cdot x\equiv 9\pmod{6}$ which is":

$x=5\cdot 9 =45\equiv 3\pmod 6$ and $15\cdot 3\equiv 27\pmod{18}\equiv 9\pmod{18} $

The other solutions are:$(9,15)$. So all solutions are these: $(3,9,15)$

Can anyone explain me how the author of the book continue the exercise?I really can't understand how he ends up with these solutions!Is there another way to reach these solutions?

I would really appreciate a thorough explanation, since I've just started working on these type of exercises and I have to clear my mind on them.

Thanks for your time !

Answer 1

The primary task is finding $5^{-1}$ modulo $6$, because once we find it, we multiply both sides by it to make $x$ have coefficient $1$ (therefore determining $x$). In general, here's how to find $z^{-1}$ modulo $a$.

• Want to find $y$ such that $zy \equiv 1 \pmod{a}$

• This is equivalent to: find $y$ and $b$ (modulo $6$) such that $zy - 1 = ab$, i.e. $xy + a(-b) = 1$. Equivalently, want to find $y$ and $b$ such that $zy + ab = 1$. These exists because of Bézout.

• To find these, use the Euclidean algorithm as in the following examples.

$1)$ $z = 24$, $a = 7$.

First divide $z$ by $a$: $24 = 3\cdot 7 + 3$. The quotient is $q_1 = 3$ and the remainder is $r_1 = 3$. Now divide $a$ by $r_1$: $7 = 2 \cdot 3 + 1$. Quotient is $q_2 = 2$ and remainder is $r_2 =1$. STOP (always stop when the remainder is $1$). Fill out a table.

$$\begin{array}{|c|c|} \hline y & b \\ \hline 1& 0\\ \hline 0 & 1 \\ \hline 1 & -3 \\ \hline -2 & 7 \\ \hline \end{array}$$

Here's how to fill out the table. Call $R_n$ the $n$th row. $R_1$ and $R_2$ are always as such. For $n\ge 3$, $R_n = R_{n-2} - q_{n-2} R_{n-1}$.

The last row has the numbers you want (so here, $y = -2$ and $b=7$).

$2)$ Your example ($a = 6$, $z = 5$).

$5 = 0\cdot 6 + 5$. So $q_1 = 0$ and $r_1 = 5$. Next $6 = 1\cdot 5 + 1$, so $r_2 = 1$ and $q_2 = 1$. STOP

$$\begin{array}{|c|c|} \hline y & b \\ \hline 1& 0\\ \hline 0 & 1 \\ \hline 1 & 0 \\ \hline -1 & 1 \\ \hline \end{array}$$

So $y = -1$ and $b = 1$.

$-1$ is $5$ modulo $6$. So $5^{-1}$ is $5$ modulo $6$. Now the author proceeds to find $x$ by multiplying both sides by $5$.

Answer 2

Note that

$$15\cdot x\equiv 27\pmod{18}\iff 15\cdot x\equiv 9\pmod{18}$$

and

$$15\cdot x\equiv 9\pmod{18}\iff 15\cdot x=9+18\cdot k\\\iff 5\cdot x=3+6\cdot k \iff 5\cdot x\equiv 3\pmod{6}$$

note also that

$$5\cdot 5\equiv 25 \equiv 1\pmod{6}$$

then

$$5\cdot x\equiv 3\pmod{6}\iff 5\cdot 5\cdot x\equiv 5\cdot3\pmod{6}\iff x\equiv 15\pmod{6}\\\iff x\equiv 3\pmod{6}$$

Answer 3

$\!\bmod 18\!:\ \overbrace{-3x\equiv 9}^{\large\ \ 15x\ \equiv\ 27}\iff -3x = 9\!+\!18j\iff x = -3\!-\!6j\iff\begin{align} x&\equiv 3\!\!\!\pmod{\!6}\\ &\equiv 3,9,15\!\!\!\pmod{\!18}\end{align}$

Answer 4

It is possible to solve this problem using algebraic symbols or augmented matrices. For example the following uses augmented matrices to solve the problem:

$$\begin{array}{c|c|c|} \hline \text{x} & \text{y} & \text{c} & \text{s} & \text{t} \\ \hline \text{15} & \text{-18} & \text{27} \\ & \text{+3} & \text{+3} & \text{-15} \\ & & & & \text{3} \\ \hline \text{5} & \text{-6} & \text{9} \\ & \text{1} & \text{1} & \text{-5} \\ \hline \text{1} & & \text{3} & \text{9} \\ & \text{1} & \text{1} & \text{-5} \\ \hline \end{array}$$

I have included animations for the construction of the augmented matrices in the PDF document "How I solved 15x≡27 (mod 18)" and a description of the "method" and its relation to the Euclidean Algorithm and the Extended Euclidean Algorithm.

Answer 5

Dividing the equivalence by $3$, then multiplying by $-1\equiv5\pmod6$: $$ 15x\equiv27\pmod{18}\\ \Updownarrow\\ 5x\equiv9\pmod{6}\\ \Updownarrow\\ x\equiv3\pmod{6} $$