# linear congruence

$$ax\equiv b\phantom{\rule{veryverythickmathspace}{0ex}}(modm),$$ |

where $a$, $b$ and $m$ are known integers and $\mathrm{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 |