0
$\begingroup$

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 Answers 1

1

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.