# a modular linear equation

• May 22nd 2008, 02:53 AM
octagonreturns
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.
• May 22nd 2008, 03:12 AM
Moo
Hello,

Quote:

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$
• Jun 3rd 2008, 08:04 AM
duggaboy
confused.
Where did the 14 come from in the final answer??
• Jun 3rd 2008, 08:06 AM
Isomorphism
Quote:

Originally Posted by duggaboy
Where did the 14 come from in the final answer??

$-81 = 19 \times (-5) + 14$
• Jun 3rd 2008, 08:46 AM
ThePerfectHacker
Quote:

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$.