Solving Linear Congruence: 12x \equiv 1(mod5)

[Ed Aboud]

Hi all.

Can someone please tell me what is going wrong here.

Solve

12x \equiv 1(mod5)


gcd(12,5) = 1

By Euclid's Algorithm =>

1 = 5.5 - 2.12

So r is 5 in this case.
x = r ( \frac{b}{d} )

Where b is 1 and d = gcd(12,5) = 1
x = 5 ( \frac{1}{1} )

x = 5

Ok fair enough but then I solve the congruence using

x \equiv b a^\phi^(^m^)^-^1 (mod m)

x \equiv (1) 12^3 (mod5)

x \equiv 3 (mod 5 )

I know this is the correct solution but what did I do wrong in the other one.

Thanks for the help!

 

[soandos]

don't know if this is valid, but isn't the first expression equivalent to <br /> 2x \equiv 1(mod5) <br />
then 2x = "6" mod 5

x\equiv 3(mod5)
yes i know that one is not supposed to do division, but modulus is prime, and there is a multiplicative inverse that i multiplied by (3)

 

[Ed Aboud]

Ok I'm not very good at this, but why is the first one equivalent to 2x \equiv 1(mod5).

Did you reduce the 12 (mod 5) ? Are you able to do that?

 

[soandos]

I think so as 12\equiv 2(mod5)