Results 1 to 2 of 2

Math Help - Congruence equation

  1. #1
    Member
    Joined
    Nov 2007
    Posts
    108

    Congruence equation

    Hope someone can help me with this problem.
    Suppose a, b, m are integers with (a,m)=1. Prove that the solution to the congruence equation ax \equiv b mod m
    is x \equiv ba^{\phi(m)-1} , \phi is Euler's function.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,408
    \begin{array}{rcll}a{\color{red}x} & \equiv & a{\color{red}ba^{\varphi (m) - 1}} & (\text{mod } m) \\  & \equiv & ba^{\varphi(m)} & (\text{mod } m) \end{array}

    You should know that a^{\varphi (m)} \equiv 1 \ (\text{mod } m) so the conclusion should follow.

    Now suppose r is any solution to ax \equiv b \ (\text{mod } m).

    So: ar \equiv ax \ (\text{mod } m) \ \Rightarrow \ r \equiv x \equiv ba^{\varphi (m) - 1} \ (\text{mod } m)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Congruence equation
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 18th 2010, 07:26 AM
  2. congruence equation
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: September 2nd 2010, 07:20 AM
  3. 2^x in a congruence equation
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 15th 2009, 06:08 PM
  4. Congruence Equation
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: December 13th 2006, 06:00 PM
  5. Congruence equation
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 15th 2006, 08:10 PM

Search Tags


/mathhelpforum @mathhelpforum