The Euclidean Algorithm: How and Why, Visually

For a nonnegative integer $n$, the greatest common divisor of $n$ and $0$ is $n$ itself. This serves as the base case for the Euclidean algorithm, terminating the recursion when the second argument becomes zero.

Conditions: $n$ is a nonnegative integer.; The pair is $(n, 0)$.

The Euclidean algorithm using division terminates when one of the entries in the current pair $(a,b)$ becomes zero. Specifically, when the remainder $r$ in the step $b=aq+r$ becomes zero, the next pair is $(0,a)$ or $(a,0)$, and the algorithm stops, returning the non-zero entry as the gcd.

Conditions: The algorithm uses the step $\gcd(a,b) = \gcd(b, a \bmod b)$.; $a$ and $b$ are nonnegative integers.; Termination occurs when the second argument is 0.

Repeating the subtraction operation reduces the magnitude of the numbers involved while preserving their common divisors. Since the numbers are positive integers, they cannot decrease indefinitely.

Conditions: The initial numbers are positive integers.; The operation is subtracting the smaller from the larger.; The goal is to preserve the gcd while reducing the numbers.

Subtracting the smaller positive integer from the larger preserves their common divisors because an integer divides both $a$ and $b$ exactly when it divides both $a$ and $b-a$. Consequently, the sets of common divisors, and hence the greatest common divisor (gcd), stay the same.

Conditions: $a$ and $b$ are positive integers.; $b > a$ (so we subtract $a$ from $b$).

The Euclidean algorithm reduces the problem size by replacing the larger number with the remainder of the division of the two numbers. Since the remainder $r$ satisfies $0 \le r < a$ (where $a$ is the divisor), the new number is strictly smaller than the previous larger number, ensuring progress towards the base case.

Conditions: The current pair is $(a,b)$ with $b \ge a > 0$.; The step computes $b = aq + r$ with $0 \le r < a$.; The new pair is $(r,a)$ or $(a,r)$ depending on implementation, but effectively the max value decreases.

The invariant property is that the set of common divisors of two numbers $a$ and $b$ is identical to the set of common divisors of $a$ and $b-a$ (or $b$ and $a \bmod b$). This ensures that the greatest common divisor (gcd) remains unchanged throughout the algorithm's steps.

Conditions: $a$ and $b$ are integers.; The operation is either subtraction ($b-a$) or modulo ($a \bmod b$).

By the definition of division with remainder, for any integers $a$ and $b$ ($b>0$), there exist unique integers $q$ and $r$ such that $a = bq + r$ and $0 \le r < b$. This constraint on $r$ ensures that the remainder is always strictly smaller than the divisor $b$, which is crucial for the algorithm's termination.

Conditions: $b$ is a positive integer.; $a$ is a nonnegative integer.; The operation is $a \bmod b$.

Replacing many subtractions by division simplifies the algorithm by using the remainder directly. For $b=aq+r$ with $0 \le r < a$, the pair $(a,b)$ is replaced by $(r,a)$.

Conditions: $a$ and $b$ are nonnegative integers.; $b = aq + r$ where $0 \le r < a$.; The algorithm proceeds by replacing the pair $(a,b)$ with $(r,a)$.