Use strong inuction to write a careful proof of Euclids divi

Use strong inuction to write a careful proof of Euclid\'s division theorem.

Solution

The Division Theorem :  Let n be a fixed integer 2. For any z Z we can find unique integers q, r such that z = qn + r where 0 r n 1.

For any k 1, if \"Euclid’s algorithm\" takes k trips to compute gcd(m, n), where m n, then n f_k+1.

By strong induction on k.

Basis: For k = 1. If we go through the loop once then certainly n 1 = f₂. And when k = 2 we went through the loop twice, so n > 1, and thus n 2 = f₃.

Induction step: Assume for all integers k that if we go through the loop k times, then n f_k+1. We must prove the same statement with k replaced by k + 1. Suppose that it takes k + 1 trips to compute gcd(m, n).

Write out the first two trips

gcd(m, n) = gcd(n, m mod n) = gcd(m mod n, n mod (m mod n))

By induction hypothesis,

m mod n f_k and

n mod (m mod n) f_k1.