Linear congruence

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!

Related Linear and Abstract Algebra News on Phys.org

soandos

don't know if this is valid, but isn't the first expression equivalent to $$2x \equiv 1(mod5)$$
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)$$

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving