Euclid’s algorithm:

Theorem 1Euclid’s algorithm: Given , , then there exist , such that .

*Proof:* We prove the statement using the principle of mathematical induction.

Denote

Fix m.

Clearly, is true.

Suppose, is true i.e. there exist m,r with such that is true.

Consider .

Since , . Hence, or

If , then , where .

Hence, there exist , such that is true.

Now, if , then .

.

, .

Hence, there exist , such that is true.

By the principle of mathematical induction, is true for all .

Advertisements