# Congruence equation

• September 28th 2008, 04:55 PM
namelessguy
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.
• September 28th 2008, 05:54 PM
o_O
$\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)$