Subjects/Algebra/Modular arithmetic/Bézout's identity26. Modular arithmeticBézout's identityLevel: intermediateIn 26. Modular arithmeticFormulaCopy LaTeXax+by=gcd(a,b)DetailConnects the greatest common divisor with integer linear combinations.Related formulasRelatedModular inverseaa−1≡1(modn)⟺gcd(a,n)=1Open formulaOpen in sectionRelatedChinese remainder theoremx≡ai(modni);N=i∏niOpen formulaOpen in section