# Prove that when computing gcd(m, n), n will always be smaller, Except for possibly on the first computation

From Donald Knuth's The Art of Computer Programming the following problem is given.

Prove that $m$ is always greater than $n$ at the begining of step E1 (see below), except possibly the first time the step occurs when computing $gcd(n,m)$.

$E1 [Find remainder]$ Divide m by n and let r be the remainder.
$E2 [Is it zero?]$ If r = 0, the algorithm terminates; $n$ is the answer.
$E3 [Reduce]& Set$m \leftarrow n, n \leftarrow r$and repeat  My question is not in how to prove this (seems fairly simple). I am just looking for a less wordy way of saying this. My proof is: After every division we have$m \leftarrow n,$and$n \leftarrow m\%n$. Thus,$n < m$based on the properties of modulo arithmetic. That is$m\%n = r : 0 < r < n$. This will hold after the first division evnen in the case where$n > m$for first iteration. After the division$m$will be less than$n$based on the information presented above. - ## 1 Answer E1. [Find remainder]: Divide$m$by$n$and let$r$be the remainder. E2. [..] E3. [Reduce]: Set$m \leftarrow n, n \leftarrow r$and repeat. It sufficed to prove that after E3,$m > n.$Observe that in step E3,$m := n, n := r$(where$:=$denoted "defined as"). So we are really after proving that$n > r$(referring to$r,n$from step E1). Recall from step E1 that$m = qn + r.$By the Division algorithm, we have$n > r.\$ QED.

This proof needs some cleanup though.

-