Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.