Results 1 to 2 of 2

Thread: 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 $\displaystyle ax \equiv b mod m$
    is $\displaystyle x \equiv ba^{\phi(m)-1}$ , $\displaystyle \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,410
    Thanks
    1
    $\displaystyle \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 $\displaystyle a^{\varphi (m)} \equiv 1 \ (\text{mod } m)$ so the conclusion should follow.

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

    So: $\displaystyle 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: Oct 18th 2010, 06:26 AM
  2. congruence equation
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: Sep 2nd 2010, 06:20 AM
  3. 2^x in a congruence equation
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Dec 15th 2009, 05:08 PM
  4. Congruence Equation
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Dec 13th 2006, 05:00 PM
  5. Congruence equation
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Oct 15th 2006, 07:10 PM

Search Tags


/mathhelpforum @mathhelpforum