Euclidean algorithm

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

Definition

The algorithm is as follows:

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

Proofs of correctness

---

TODO: These proofs

---

The algorithm terminates

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

The algorithm computes the GCD

Equally important is the proof that the algorithm always outputs the GCD of [ilmath]a[/ilmath] and [ilmath]b[/ilmath]

See next

• Extended Euclidean algorithm

See also

• GCD
• Divisor
• Division algorithm