linear congruence

The linear congruence

$$ax\equiv b(modm),$$

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^{\phi (m)-1}b,$$

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

Solving the linear congruence also gives the solution of the Diophantine equation

$$ax-my=b,$$

and conversely.  If  $x=x_0$,  $y=y_0$  is a solution of this equation, then the general solution is

$$\{\begin{array}{cc}x=x_0+km,\hfill & \\ y=y_0+ka,\hfill & \end{array}$$

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

Title	linear congruence
Canonical name	LinearCongruence
Date of creation	2013-03-22 14:18:15
Last modified on	2013-03-22 14:18:15
Owner	Mathprof (13753)
Last modified by	Mathprof (13753)
Numerical id	15
Author	Mathprof (13753)
Entry type	Definition
Classification	msc 11A41
Synonym	first degree congruence
Related topic	QuadraticCongruence
Related topic	SolvingLinearDiophantineEquation
Related topic	GodelsBetaFunction
Related topic	ConditionalCongruences