# Euclidean Algorithm

Prove the Euclidean Algorithm:

Let n be a natural

number, and let q be a positive number. Then there exist natural

numbers m, r such that 0 < or = r < q and n=mq+r

Show that m and r exist and are also unique.

**Fix q and induct on n, and note that you can only use rules of addition

© BrainMass Inc. brainmass.com October 10, 2019, 4:15 am ad1c9bdddfhttps://brainmass.com/math/discrete-math/euclidean-algorithm-453431

#### Solution Preview

Proof:

Since q is a positive number, then q>=1.

If q = 1, then for any natural number n, we must have n = n*1 = nq. Let m = n, r = 0, then m, q are natural numbers and n = mq + r.

Now we consider q>=2 and make induction on n.

If n = 0, then we can set m = 0, r = 0 and we ...

#### Solution Summary

The expert examines Euclidean Algorithm.

$2.19