# Greatest Common Divisor

$g(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.

- If $a$ and $b$ are not both zero, an integer $d>0$ is the greatest common divisor of $a$ and $b$, written $d=g(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≤d$.

- If $a$ and $b$ are both zero, we define $g(a,b)=g(0,0)=0$.

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

See EEA for computing the GCD.

### Propositions and Theorems

**Proposition 1**
For all real numbers $x$, we have $x≤∣x∣$

**Bounds By Divisibility (BBD)**
For all integers $a$ and $b$, if $b∣a$ and $a=0$ then $b≤∣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≤r<b$

**GCD With Remainders (GCD WR)**
For all integers $a$, $b$, $q$ and $r$, if $a=qb+r$, then $g(a,b)=g(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=g(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=g(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∣g(a,b)$.

**Coprimeness Characterization Theorem (CCT)**
For all integers $a$ and $b$, $g(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, $g(da ,db )=1$, where $d=g(a,b)$

**Coprimeness and Divisibility (CAD)**
For all integers $a$, $b$ and $c$, if $c∣ab$ and $g(a,c)=1$, then $c∣b$.