TAOCP 1.1 Exercise 2
We prove by examining the structure of Algorithm E that $m \ge n$ holds at the beginning of step E1, except possibly at the first execution of that step.
Exercise 2. [15] Prove that $m$ is always greater than $n$ at the beginning of step E1, except possibly the first time this step occurs.
Verified: yes
Solve time: 1m05s
We prove by examining the structure of Algorithm E that $m \ge n$ holds at the beginning of step E1, except possibly at the first execution of that step. Consider the initial values of $m$ and $n$ supplied to the algorithm. If $m \ge n$ initially, there is nothing to prove, since the first occurrence of E1 already satisfies $m \ge n$. If $m < n$ initially, then when step E1 is executed the first time, it is possible that $m < n$, as in the example $m = 119$, $n = 544$ given in the text. Hence the exception "possibly the first time" is necessary.
Suppose that E1 is being executed for the second or any later time. Then in the immediately preceding execution of step E3, the algorithm sets
$m \leftarrow n, \quad n \leftarrow r,$
where $r$ is the remainder from the previous division of $m$ by $n$. By the definition of remainder in step E1, we have
$0 \le r < n.$
Thus, after step E3, the new values of $m$ and $n$ satisfy
$m \leftarrow n > r \leftarrow n,$
so $m > n$ at the beginning of the next execution of step E1. Therefore, once E1 has been executed at least once, it follows from the replacement operations in E3 and the properties of the remainder that $m \ge n$ always holds at the beginning of subsequent executions of E1.
This completes the proof.
∎