Bezout's Identity & Extended Euclidean Algorithm Cheat Sheet

Key Facts

• Bézout's Identity states that for integers $a$ and $b$, not both zero, there exist integers $x$ and $y$ such that $ax + by = \gcd(a,b)$.
• The Euclidean Algorithm uses repeated division: $a = bq + r$, where $0 \le r < |b|$, then replaces $(a,b)$ with $(b,r)$.
• The last nonzero remainder in the Euclidean Algorithm is $\gcd(a,b)$.
• The Extended Euclidean Algorithm rewrites remainders backward until $\gcd(a,b)$ is expressed as $ax + by$.
• If $\gcd(a,b)=1$, then $a$ and $b$ are relatively prime and there exist integers $x$ and $y$ such that $ax + by = 1$.
• A linear Diophantine equation $ax + by = c$ has integer solutions exactly when $\gcd(a,b)$ divides $c$.
• If $ax + by = \gcd(a,b)$, then multiplying by $\frac{c}{\gcd(a,b)}$ gives one solution to $ax + by = c$ when $\gcd(a,b) \mid c$.
• If $ax + my = 1$, then $x$ is a modular inverse of $a$ modulo $m$, so $a^{-1} \equiv x \pmod{m}$.

Vocabulary

Greatest common divisor

The greatest common divisor $\gcd(a,b)$ is the largest positive integer that divides both $a$ and $b$.

Bézout coefficients

Bézout coefficients are integers $x$ and $y$ that satisfy $ax + by = \gcd(a,b)$.

Euclidean Algorithm

The Euclidean Algorithm is a repeated division process used to find $\gcd(a,b)$ efficiently.

Extended Euclidean Algorithm

The Extended Euclidean Algorithm finds both $\gcd(a,b)$ and integers $x$ and $y$ such that $ax + by = \gcd(a,b)$.

Relatively prime

Two integers $a$ and $b$ are relatively prime when $\gcd(a,b)=1$.

Modular inverse

A modular inverse of $a$ modulo $m$ is a number $x$ such that $ax \equiv 1 \pmod{m}$.