# Math Help - a modular linear equation

1. ## a modular linear equation

Hello,

I have to solve this modular linear equation (in paper not using programming)

18x = 81 (mod171)

My thought is we begin using the extended euclidean algorithm (ax+by=gcd(a,b) calculating : (div a/b), the gcd(a,b) and the x,y

An Example Using the Extended Euclidean Algorithm

I know this isn't a short exercise so thanks in advance for looking and trying to help. Meanwhile I'm doing my best searching & trying to understand.

2. Hello,

Originally Posted by octagonreturns
Hello,

I have to solve this modular linear equation (in paper not using programming)

18x = 81 (mod171)

My thought is we begin using the extended euclidean algorithm (ax+by=gcd(a,b) calculating : (div a/b), the gcd(a,b) and the x,y

An Example Using the Extended Euclidean Algorithm

I know this isn't a short exercise so thanks in advance for looking and trying to help. Meanwhile I'm doing my best searching & trying to understand.
First of all, divide by 9 :

$18x=81 \mod 171 \Longleftrightarrow 18x=81+171k$

It yields $2x=9+19k$

So you want to solve for x in $2x=9 \mod 19$

Now, use the Euclidian algorithm, to find u and v such that $2u+19v=1 \longleftrightarrow 2u=1 \mod 19$ (this is possible because 2 and 19 are coprime)
Then, we'll multiply by 9 to get : $2x=9 \mod 19$, where x=9u.

---------------------

$19=2*9+1 \rightarrow 1=19+2*(-9)$

So u=-9

Hence $x=-81=\boxed{14} \mod 19$

3. ## confused.

Where did the 14 come from in the final answer??

4. Originally Posted by duggaboy
Where did the 14 come from in the final answer??
$-81 = 19 \times (-5) + 14$

5. Originally Posted by octagonreturns
18x = 81 (mod171)
Note that $\gcd(18,171)=9$.

If we can find a solution $x_0$ then all other solutions (in different congruence classes) shall be given by $x_0 + t\cdot \tfrac{171}{9} = x_0+ 19t$ whete $0\leq t\leq 8$. It remains to find a solution $x_0$. You can do what Moo did to get $x_0 = 14$. Thus, the other solutions are given by $14,33,52,71,90,109,128,147$.