1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Linear congruence

  1. Nov 19, 2008 #1
    Hi all.

    Can someone please tell me what is going wrong here.


    [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!
  2. jcsd
  3. Nov 19, 2008 #2
    don't know if this is valid, but isn't the first expression equivalent to [tex]
    2x \equiv 1(mod5)
    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)
  4. Nov 19, 2008 #3
    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?
  5. Nov 19, 2008 #4
    I think so as [tex]12\equiv 2(mod5)[/tex]
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?