# linear congruence

 $ax\equiv b\pmod{m},$

where $a$, $b$ and $m$ are known integers and  $\gcd{(a,\,m)}=1$,  has exactly one solution $x$ in $\mathbb{Z}$, when numbers congruent to each other are not regarded as different.  The solution can be obtained as

 $x=a^{\varphi(m)-1}b,$

where $\varphi$ means Euler’s phi-function.

Solving the linear congruence also gives the solution of the

 $ax\!-\!my=b,$

and conversely.  If  $x=x_{0}$,  $y=y_{0}$  is a solution of this equation, then the general solution is

 $\begin{cases}x=x_{0}\!+\!km,\\ y=y_{0}\!+\!ka,\\ \end{cases}$

where  $k=0$, $\pm 1$, $\pm 2$, …

Title linear congruence LinearCongruence 2013-03-22 14:18:15 2013-03-22 14:18:15 Mathprof (13753) Mathprof (13753) 15 Mathprof (13753) Definition msc 11A41 first degree congruence QuadraticCongruence SolvingLinearDiophantineEquation GodelsBetaFunction ConditionalCongruences