1.11

Claim. For positive integers with x > y, [math]\displaystyle{gcd(x,y)=gcd(y,\;x\!\bmod\! y)}[/math].

Proof. Let [math]\displaystyle{r=x\bmod y}[/math] and write [math]\displaystyle{x=q\,y+r}[/math] with [math]\displaystyle{0\le r<y}[/math]. 1. If [math]\displaystyle{d=gcd(x,y)}[/math], then [math]\displaystyle{d\mid x}[/math] and [math]\displaystyle{d\mid y}[/math], so [math]\displaystyle{d\mid(x-qy)=r}[/math]. Thus [math]\displaystyle{d}[/math] divides both y and r, giving [math]\displaystyle{d\le gcd(y,r)}[/math]. 2. Conversely, if [math]\displaystyle{d'=gcd(y,r)}[/math], then [math]\displaystyle{d'\mid y}[/math] and [math]\displaystyle{d'\mid r}[/math], hence [math]\displaystyle{d'\mid(qy+r)=x}[/math]. Therefore [math]\displaystyle{d'\le gcd(x,y)}[/math]. Because each divides the other, the two gcd values are equal, establishing the invariant step of Euclid’s algorithm.

Termination. The remainder sequence [math]\displaystyle{y > r_1 > r_2 > \dots \ge 0}[/math] is strictly decreasing and non-negative, so after at most y steps a remainder 0 appears. When the second argument is 0, the algorithm returns the first argument, which by the invariant is the common divisor of every previous pair—hence the greatest common divisor of the original inputs.

Pseudocode. gcd(x, y):
  while y ≠ 0:
    x, y = y, x % y
  return x
Each loop iteration preserves the gcd and reduces the second operand, so the function terminates and returns the correct [math]\displaystyle{gcd(x,y)}[/math]. ∎

Back to Chapter 1 .