Euclidean algorithm

Note: this is an algorithm for computing the GCD of two positive integers

Definition

The algorithm is as follows:

Input	$a,b\in\mathbb{N}_+$, such that $a\ge b$ (swap them around if $a< b$)
Output	The GCD of $a$ and $b$
Process	Let $A=a$ Let $B=b$ Let $R=$ the remainder of $A\div B$ (see Division algorithm) If $R=0$ then: RETURN: $B$ (we have $B=\text{gcd}(a,b)$) Let $A=B$ Let $B=R$ Goto step 3

Proofs of correctness

---

TODO: These proofs

---

The algorithm terminates

Given this algorithm loops until $R=0$ it is important to know for certain that eventually we will have $R=0$

The algorithm computes the GCD

Equally important is the proof that the algorithm always outputs the GCD of $a$ and $b$

See next

• Extended Euclidean algorithm

See also

• GCD
• Divisor
• Division algorithm