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.