Thread: 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.

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 :



It yields

So you want to solve for x in

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

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



So u=-9

Hence

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

Originally Posted by duggaboy

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

Originally Posted by octagonreturns

18x = 81 (mod171)

Note that .

If we can find a solution then all other solutions (in different congruence classes) shall be given by whete . It remains to find a solution . You can do what Moo did to get . Thus, the other solutions are given by .