Linear congruence

  • Thread starter Ed Aboud
  • Start date
197
0
Hi all.

Can someone please tell me what is going wrong here.

Solve

[tex] 12x \equiv 1(mod5) [/tex]


[tex]gcd(12,5) = 1 [/tex]

By Euclid's Algorithm =>

[tex] 1 = 5.5 - 2.12 [/tex]

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

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

[tex] x = 5 [/tex]

Ok fair enough but then I solve the congruence using

[tex] x \equiv b a^\phi^(^m^)^-^1 (mod m) [/tex]

[tex] x \equiv (1) 12^3 (mod5) [/tex]

[tex] x \equiv 3 (mod 5 ) [/tex]

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

Thanks for the help!
 
166
0
don't know if this is valid, but isn't the first expression equivalent to [tex]
2x \equiv 1(mod5)
[/tex]
then 2x = "6" mod 5

[tex]x\equiv 3(mod5)[/tex]
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)
 
197
0
Ok I'm not very good at this, but why is the first one equivalent to [tex] 2x \equiv 1(mod5) [/tex].

Did you reduce the 12 (mod 5) ? Are you able to do that?
 
166
0
I think so as [tex]12\equiv 2(mod5)[/tex]
 

Related Threads for: Linear congruence

  • Posted
Replies
7
Views
7K
Replies
4
Views
2K
Replies
1
Views
4K
  • Posted
Replies
3
Views
2K
  • Posted
Replies
23
Views
4K
  • Posted
Replies
3
Views
3K
  • Posted
Replies
19
Views
3K
  • Posted
Replies
1
Views
2K

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
Top