linear congruence

The linear congruence


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


where φ means Euler’s phi-function.

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


and conversely.  If  x=x0,  y=y0  is a solution of this equation, then the general solution is


where  k=0, ±1, ±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