Euclidean Algorithm

euclidean algorithm

Let

m, n \in N_{1}

such that

m >; n

, if

m % n >; 0

, then

gcd (m, n) = gcd (n, m % n)

. Otherwise if

m % n = 0

, then

n | m

and

gcd (m, n) = n

If $m % n = 0$ , then $m = (m / / n) \cdot n$ , therefore $gcd (m, n) = gcd ((m / / n) \cdot n, n) = n$ , so now assume that $m % n >; 0$

Recall that $m = (m / / n) \cdot n + m % n$ , therefore $m - (m / / n) \cdot n = m % n$ , so that if $d$ divides both $m, n$ , then it must divide $m % n$ (and clearly $n$ ), and by the original equation if $d$ is a divisor of both $n, m % n$ then $d$ divides $m$ (and clearly $n$ ).

The above paragraph shows that a number is a divisor of $m, n$ if and only if it is a divisor of $n, m % n$ , which shows that their set of divisors are equal and thus $gcd (m, n) = gcd (n, m % n)$

bounded sum implies one less then half

Suppose that

x, y, b \in N_{1}

and

x <; y

with

x + y \leq b

, then

x <; \frac{b}{2}

Suppose for the sake of contradiction that

x \geq \frac{b}{2}

, then we know that

y >; x \geq \frac{b}{2}

so therefore

x + y > \frac{b}{2} + \frac{b}{2} = b

, so we have

x + y >; b

which is a contradiction so that

x <; \frac{b}{2}

euclidean algorithm has exponentially decreasing remainders

Let

a, b \in N_{1}

with

a \geq b

be two integers, and suppose we will preform the euclidean algorithm on them to compute

gcd (m, n)

, supposing that

r_{k}

represents the remainder after

k

(where

k \in N_{1}

) steps into the euclidean algorithm, then

r_{2 n} < \frac{b}{2^{n}}

For the base case, suppose that $n = 1$ , so we'd like to prove that $r_{2} < \frac{b}{2}$ . Firstly we know that $a = b q_{0} + r_{0}$ with $0 \leq r_{0} < b$ , then applying the next iteration we have $b = r_{0} q_{1} + r_{1}$ with $0 \leq r_{1} < r_{0}$ and one more time, we get $r_{0} = r_{1} q_{2} + r_{2}$ with $0 \leq r_{2} < r_{1}$ , this shows us that $b = (r_{1} q_{2} + r_{2}) q_{1} + r_{1}$ .

Since $a \geq b$ , $b > r_{0}$ and $r_{0} > r_{1}$ , then $q_{0} \geq 1$ , $q_{1} \geq 1$ and $q_{2} \geq 1$ , therefore $b = (r_{1} q_{2} + r_{2}) q_{1} + r_{1} \geq (r_{1} \cdot 1 + r_{2}) \cdot 1 + r_{1} \geq r 1 + r 2$ therefore $r_{2} <; \frac{b}{2}$ which concludes the base case

Now let $k \in N_{1}$ assuming that $r_{2 k} \leq \frac{b}{2^{k}}$ , we want to prove that $r_{2 (k + 1)} = \frac{b}{2^{k + 1}}$ , noting that $2 (k + 1) = 2 k + 2$ .

To start let's say we have an intance of the euclidean algorithm that lasts for at least $2 k + 2$ iterations, therefore we know that $r_{2 k} \leq \frac{b}{2^{k}}$ by our induction hypothesis, additionally at the $2 k$ -th iteration we would have an equation of the form $r_{2 k} = r_{2 k + 1} (q_{2 k + 2}) + r_{2 k + 2}$ , since we know that $r_{2 k + 1} >; r_{2 k + 2}$ , then $q_{2 k + 2} \geq 1$ , which then shows that $r_{2 k} = r_{2 k + 1} (q_{2 k + 2}) + r_{2 k + 2} \geq r_{2 k + 1} + r_{2 k + 1}$ , and since $\frac{b}{2^{k}} > r_{2 k}$ , then we know that $r_{2 k + 2} < \frac{1}{2} \cdot \frac{b}{2^{k}} = \frac{b}{2^{k + 1}}$ which is what we needed to show

upper bound on euclidean algorithm iterations

The euclidean algorithm terminates in at most

2 \log_{2} (b)

iterations

The euclidean algorithm terminates in

k

iterations if and only if

r_{k} = 0

, we know that for all

n \in N_{1}

that

r_{2 n} < \frac{b}{2^{n}}

, therefore when

n = \log_{2} (b)

, then we have

r_{2 \log_{2} (b)} < \frac{b}{2^{\log_{2} (b)}} = \frac{b}{b} = 1

, but if

r_{2 \log_{2} (b)} < 1

, then since the remainders are always elements of

N_{0}

, then we know that

r_{2 \log_{2} (b)} = 0

, thus we've shown after

2 \log_{2} (b)

iterations the algorithm must terminate