---
title: "Euclidean Algorithm"
source: https://www.jemoka.com/posts/kbheuclidean_algorithm/
---

A corollary of greatest common divisor and division.
Say you have some \(b|a\) such that:
\begin{equation} a = bq + r \end{equation}
Now, \(d|a,b \Leftrightarrow d|b,r\) (because \(d|b,r\) implies there&rsquo;s some \(x, x&rsquo;\) such that \(a = (dx)q+dx&rsquo;\), and so \(a = d(xq + x&rsquo;)\) and so \(d|a\); the logic goes the other way too).
This finally implies that \(\gcd (a,b)= \gcd (b,r)\) because any divisor that works for one works for both.
