Greatest Common Divisor

$\gcd (a,b)$ is the largest integer that is both a divisor of $a$ and a divisor of $b$. GCD Definition: Let $a$ and $b$ be integers.

1. If $a$ and $b$ are not both zero, an integer $d>0$ is the greatest common divisor of $a$ and $b$, written $d=\gcd (a,b)$, when
   • $d$ is a common divisor of $a$ and $b$,and
   • for all integers $c$, if $c$ is a common divisor of $a$ and $b$, then $c\le d$.
2. If $a$ and $b$ are both zero, we define $\gcd (a,b)=\gcd (0,0)=0$.

Coprime Definition: Two integers $a$ and $b$ are coprime if $\gcd (a,b)=1$

See EEA for computing the GCD.

Propositions and Theorems

Proposition 1 For all real numbers $x$, we have $x\le |x|$

Bounds By Divisibility (BBD) For all integers $a$ and $b$, if $b|a$ and $a\ne 0$ then $b\le |a|$.

Division Algorithm (DA) For all integers $a$ and positive integers $b$, there exist unique integers $q$ and $r$ such that $a=qb+r,0\le r<b$

GCD With Remainders (GCD WR) For all integers $a$, $b$, $q$ and $r$, if $a=qb+r$, then $\gcd (a,b)=\gcd (b,r)$.

This is used with the Extended Euclidean Algorithm (EEA).

GCD Characterization Theorem (GCD CT) For all integers $a$ and $b$, and non-negative integers $d$, if

• $d$ is a common divisor of $a$ and $b$, and
• there exist integers $s$ and $t$ such that $as+bt=d$,

then $d=\gcd (a,b)$.

Bézout/Bezout’s Lemma (BL) (IMPORTANT) For all integers $a$ and $b$, there exist integers $s$ and $t$ such that $as+bt=d$, where $d=\gcd (a,b)$. → Linear Diophantine Equation

Common Divisor Divides GCD (CDD GCD) For all integers $a$, $b$ and $c$, if $c|a$ and $c|b$, then $c|\gcd (a,b)$.

Coprimeness Characterization Theorem (CCT) For all integers $a$ and $b$, $\gcd (a,b)=1$ if and only if there exist integers $s$ and $t$ such that $as+bt=1$.

Division by the GCD (DB GCD) For all integers $a$ and $b$, not both zero, $\gcd (\frac{a}{d},\frac{b}{d})=1$, where $d=\gcd (a,b)$

Coprimeness and Divisibility (CAD) For all integers $a$, $b$ and $c$, if $c|ab$ and $\gcd (a,c)=1$, then $c|b$.

Related

• Extended Euclidean Algorithm (EEA)
• Linear Diophantine Equation