Question

Questions about the algorithm within the link: http://codepad.org/hIgXHxwh (it's euclid's algorithm implemented in C).

Prove that the value of m is always greater than the value of n the first time "remainder = m % n" is computed

Answer 1

Prove that the value of m is always greater than the value of n when "remainder = m % n" is computed, EXCEPT the first time it is computed :-P sorry

Answer 2

so... sometimes, they are equal values the first time that step in the algorithm is computed and the function returns 0

Answer 3

but every other time the value of m is bigger than n

Answer 4

this is like the first page in uncle knuth's book

Answer 5

After the mod operation m takes the value of n, and n takes the value of the remainder. So you're really asking why the remainder when dividing by n is strictly less than n. Define % to be the operator that returns the smallest nonnegative remainder when dividing two numbers.

Suppose there exist positive integers m and n such that m % n >= n. Let m % n = r. Then we can express m as m = qn + r. But r >= n, so r = n + t for some nonnegative integer t. Since t = r - n, and n is positive, then t < r.
m = qn + r = qn + n + t = (q + 1)n + t
Thus we've found a smaller remainder than r. But that contradicts our assumption. Thus m % n < n for all positive integers m and n.

Answer 6

that's exactly the answer the book was looking for :-D thanks