Home/Algebra/Modular arithmetic/Bézout's identity26. Modular arithmeticBézout's identityLevel: intermedioIn 26. Modular arithmeticFormulaCopy LaTeXax+by=gcd(a,b)ax+by=\gcd(a,b)ax+by=gcd(a,b)Tagsalgebraarithmetic modularCSalgebra formulamodularDetailConnects the greatest common divisor with integer linear combinations.Found an error? Contact us.Related formulasRelatedModular inverseaa−1≡1(modn) ⟺ gcd(a,n)=1aa^{-1}\equiv1\pmod n\iff\gcd(a,n)=1aa−1≡1(modn)⟺gcd(a,n)=1Open formulaOpen in sectionRelatedChinese remainder theoremx≡ai(modni);N=∏inix\equiv a_i\pmod{n_i};\quad N=\prod_i n_ix≡ai(modni);N=i∏niOpen formulaOpen in section