## You are here

Homelinear congruence

## Primary tabs

# linear congruence

The linear congruence

$ax\equiv b\;\;(\mathop{{\rm mod}}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,$ |

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{cases}x=x_{0}\!+\!km,\\ y=y_{0}\!+\!ka,\\ \end{cases}$ |

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

Related:

QuadraticCongruence, SolvingLinearDiophantineEquation, GodelsBetaFunction, ConditionalCongruences

Synonym:

first degree congruence

Major Section:

Reference

Type of Math Object:

Definition

Parent:

## Mathematics Subject Classification

11A41*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections