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 ad1c9bdddf
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 ...
The expert examines Euclidean Algorithm.