The Euclidean algorithm and Lame’s theorem´

[Pages:3]The Euclidean algorithm and Lame?'s theorem

1 The Euclidean algorithm

Suppose a and b are a pair of integers. We will assume, furthermore, that a and b are both positive and that a b. Lemma 1.1. If a and b are both non-zero positive integers with a > b, then we may write a = qb+r, and the following equality holds

gcd(a, b) = gcd(b, r). Proof. First, let d = gcd(a, b). Since d|a and d|b, it follows that d|a-qb = r. Thus, gcd(a, b)|gcd(b, r). Now, if c is any common divisor of b and r, then c necessarily also divides qb + r. In other words, c|a as well. Thus, c|b an c|a, which means that c|d. In particular gcd(b, r)|gcd(a, b) and thus gcd(a, b) = gcd(b, r).

Using this fact, we may now use the division algorithm to produce the gcd of two integers. Construction 1.2 (Euclidean algorithm). Indeed, take a and b positive integers with a > b. To make the recursive nature of the discussion clear we write it as follows. Set a = r0 and b = r1. Set i = 0.

1. Using the division algorithm, write ri = qi+1ri+1 + ri+2.

where 0 ri+2 < ri+1. 2. If ri+2 = 0, then gcd(r0, r1) = r1 and we output r2 and stop, else go to the next step. 3. If ri+2 = 0, then 0 < ri+2 < ri+1. In the case, increment i and go back to Step 1. Theorem 1.3. The Euclidean algorithm terminates. Proof. At each iteration of the Euclidean algorithm, we produce an integer ri. Since 0 ri+1 < ri by construction, the sequence ri is a strictly decreasing sequence of positive numbers and thus must eventually be 0.

2 Analyzing the running time of the Euclidean algorithm

The naive argument about termination of the Euclidean algorithm implies that it terminates in at most b steps, since there are at most b integers between 0 and b - 1. However, doing a few examples should make it clear that typically the algorithm terminates in significantly fewer than b steps. To further analyze we make more observations about the integers qi and ri above.

1

2

2 Analyzing the running time of the Euclidean algorithm

Lemma 2.1. The sequence q1, . . . , qn of quotients produced in the division algorithm have the property that qi 1 and qn 2.

Proof. We will prove qn 2. At the last step of the division algorithm, we have rn-1 = qnrn. The division algorithm tells us that rn < rn-1. Thus, qn 2.

Now, we go backwards in the division algorithm. Indeed, rn 1. Then, rn-1 2rn 2. At the next step, rn-2 = qn-1rn-1 + rn-2. Since qn-1 1, it follows that

rn-2 = qn-1rn-1 + rn rn-1 + rn 1 + 2 = 3.

At the next stage, again we see that

rn-3 = qn-2rn-2 + rn-1 rn-2 + rn-1 = 3 + 2 = 5.

At each stage, we see that

ri = qi-1ri-1 + ri-2 ri-1 + ri-2.

Let fi be the i-th Fibonacci number, where f0 = 1, f1 = 1 Now, rn 1 = f1. Likewise rn-1 2 = f2, and rn-2 3 = f3. The inequality above shows that

ri ri-1 + ri-2.

Proposition 2.2. For any integer i 0, ri fn+1-i.

Proof. We proceed by induction. In the case i = n, f1 = 1 and r0 f1 = 1. Now assume inductively that ri fn+1-i for each i > k. Consider

rn-k = qn-k-1rn-k-1+rn-k-2 rn-k-1+rn-k-2 fn+1-(n-k-1)+fn+1-(n-k-2) = fn-k+fn-k-1 = fn-k+1.

Thus, by induction, we conclude that ri fn+1-i.

Iterating this observation, we conclude that, if the Euclidean algorithm terminates after n steps,

then r1 in the division algorithm must be at least fn, i.e., b must be at least as large as fn. Thus, the

question we are interested in is, how large is fn? For example, how many digits does it have? To answer this question we want to consider log10b = log10fn (since log1010k = k, this number grows

roughly as the number of digits).

To answer the question about the size of log10fn, we can appeal to our formula for the n-th

Fibonacci

number.

Recall

that

if

?

=

-1? 2

5 , then

fn

=

1

5

(-1)n+1(n-+1

- n++1).

If we

set ?

:=

1? 2

5,

then

the

above

formula

may

also

be

written

as

fn

=

1 5

(+n+1

-

-n+1).

3

2 Analyzing the running time of the Euclidean algorithm

Notice than 1

that + > in absolute

1, while - is negative, but smaller value. Since 5 > 4, we know that

th5an>1.2I,napnadrttihcuuslatrh,at -n+11

5

is <

always smaller

1 2

.

Now,

fn

is

always an integer. The formula above thus shows that fn is the largest integer smaller than

n++1

+

1 .

52

Therefore, its rate of growth is bounded by n++1 . In particular, we see that

5

log10fn

log10

(

+n+1 5

)

=

(n

+

1)log10+

-

log10( 5).

The leading term here n log10 + (as the other term is constant). So, it suffices to estimate log10+,

which we now do. Since we're interested in computing log10+, it suffices to find the first power

of + which is bigger than 10 (take logarithms of both sides!).

Note that + is a root of x2 - x - 1, i.e., +2 = + + 1. Therefore, +3 = +2 + + = 2+1.

Likewise, +4 = Since 2 < 5,

2+2 + we see

+ that

= 3+ + >

+ 2, and +5 =

3 2

,

so

5+

+

3

3+2 + 2+

=

5+3.

Now, +

=

1+ 2

5.

>

21 2

> 10.

It follows immediately that

log10+5

=

5 log10 +

=

log10(5 + 3)

>

log1010

=

1.

In other

words,

log10+

>

1 5

.

Putting

everything together we have deduced the following fact.

Theorem 2.3 (Lame?). The number of steps n in the Euclidean algorithm grows at the same rate as

n 5log10b.

In other words, the number of steps in the Euclidean algorithm grows at about 5 times the rate of the number digits of b.

Proof. Putting the various steps of the analysis above together, we see that:

1

asoklog10b

log10fn

n log10

+

n. 5

Remark 2.4. In fact, our analysis gives us something much better. We see how to produce versions of the Eucliden algorithm that runs slowly using Fibonacci sequences. In fact, it turns out that one can use Fibonacci numbers to produce numbers for which the Euclidean algorithm takes about 5 times the number of digits in b number of steps. Nevertheless, for a given pair a and b, the algorithm can run much faster (for an extreme example, take a = b!). What we've really done is describe the number of steps in a worst case scenario. Moreover, more precise estimates for log10+ would yield more precise information about the number of steps required.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download