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]
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook