Applied Number Theory
Professor Ellen Gethner
February 2, 2016
Euclidean Algorithm; supplementary material for week 3
Warmup: The Division Algorithm (not really an algorithm)
Division Algorithm. For any a, b Z+ with a b, unique
integers q and r such that
Warmup: The Division Algorithm (not really an algorithm)
Division Algorithm. For any a, b Z+ with a b, unique
integers q and r such that
a = bq + r with 0 r < b.
Warmup: The Division Algorithm (not really an algorithm)
Division Algorithm. For any a, b Z+ with a b, unique
integers q and r such that
a = bq + r with 0 r < b.
Trivia. q stands for quotient and r stands for remainder.
Warmup: The Division Algorithm (not really an algorithm)
Division Algorithm. For any a, b Z+ with a b, unique
integers q and r such that
a = bq + r with 0 r < b.
Trivia. q stands for quotient and r stands for remainder.
The proof can be found in any Discrete Math textbook (or
ask me).
Warmup, continued.
I
A direct and easy-to-prove consequence of the Division
Algorithm is the following.
Warmup, continued.
I
A direct and easy-to-prove consequence of the Division
Algorithm is the following.
Theorem D. If a, b, c, d, r , s Z with d 6= 0 such that d|a
and d|b then d|(ra + sb).
Warmup, continued.
I
A direct and easy-to-prove consequence of the Division
Algorithm is the following.
Theorem D. If a, b, c, d, r , s Z with d 6= 0 such that d|a
and d|b then d|(ra + sb).
It then follows that d|(a + b), d|(a b) and d|ra (among
many other things...).
Warmup, continued.
I
A direct and easy-to-prove consequence of the Division
Algorithm is the following.
Theorem D. If a, b, c, d, r , s Z with d 6= 0 such that d|a
and d|b then d|(ra + sb).
It then follows that d|(a + b), d|(a b) and d|ra (among
many other things...).
In other words, if d divides both a and b, then d divides any
integer linear combination of a and b. The above are just a
few special cases.
Warmup, greatest common divisor
I
Definition. Let a, b Z+ . The greatest common divisor of a
and b, written gcd(a, b), is the largest positive integer d that
divides both a and b.
Warmup, greatest common divisor
I
Definition. Let a, b Z+ . The greatest common divisor of a
and b, written gcd(a, b), is the largest positive integer d that
divides both a and b.
That is, gcd(a, b) = d.
Warmup, greatest common divisor
I
Definition. Let a, b Z+ . The greatest common divisor of a
and b, written gcd(a, b), is the largest positive integer d that
divides both a and b.
That is, gcd(a, b) = d.
Example 1. gcd(4, 6) = 2, gcd(3, 7) = 1, gcd(100, 4) = 4,
and gcd(100001, 0) = 100001, etc.
Warmup, greatest common divisor
I
Definition. Let a, b Z+ . The greatest common divisor of a
and b, written gcd(a, b), is the largest positive integer d that
divides both a and b.
That is, gcd(a, b) = d.
Example 1. gcd(4, 6) = 2, gcd(3, 7) = 1, gcd(100, 4) = 4,
and gcd(100001, 0) = 100001, etc.
One place (of many) where gcd is needed is in RSA
encryption.
Warmup, greatest common divisor
I
Definition. Let a, b Z+ . The greatest common divisor of a
and b, written gcd(a, b), is the largest positive integer d that
divides both a and b.
That is, gcd(a, b) = d.
Example 1. gcd(4, 6) = 2, gcd(3, 7) = 1, gcd(100, 4) = 4,
and gcd(100001, 0) = 100001, etc.
One place (of many) where gcd is needed is in RSA
encryption.
Thus the actual computation of gcd(a, b) is necessary and
important.
Example 2. (Illustration of the Euclidean Algorithm)
Problem. Find gcd(54, 21). That is, compute d = gcd(54, 21)
where a = 54 and b = 21.
I
54 = 2 21 + 12 and note that
I
0 12 < 21 and by Theorem D that
d|12 because d|54 and d|21.
Example 2. (Illustration of the Euclidean Algorithm)
Problem. Find gcd(54, 21). That is, compute d = gcd(54, 21)
where a = 54 and b = 21.
I
54 = 2 21 + 12 and note that
I
0 12 < 21 and by Theorem D that
d|12 because d|54 and d|21.
For notational purposes, let r1 = 12, and q1 = 2, where r1
stands for the first remainder and q1 stands for the first
quotient.
Euclidean algorithm example, continued
I
21 = 1 12 + 9 and note that
I
0 9 < 12 and by Theorem D, that
d|9 because d|12 and d|21.
Euclidean algorithm example, continued
I
21 = 1 12 + 9 and note that
I
0 9 < 12 and by Theorem D, that
d|9 because d|12 and d|21.
For notational purposes, let r2 = 9, and q2 = 1, where r2
stands for the second remainder and q2 stands for the second
quotient.
Euclidean algorithm example, continued
I
21 = 1 12 + 9 and note that
I
0 9 < 12 and by Theorem D, that
d|9 because d|12 and d|21.
For notational purposes, let r2 = 9, and q2 = 1, where r2
stands for the second remainder and q2 stands for the second
quotient.
12 = 1 9 + 3 d|3 (q3 = 1, r3 = 3)
Euclidean algorithm example, continued
I
21 = 1 12 + 9 and note that
I
0 9 < 12 and by Theorem D, that
d|9 because d|12 and d|21.
For notational purposes, let r2 = 9, and q2 = 1, where r2
stands for the second remainder and q2 stands for the second
quotient.
12 = 1 9 + 3 d|3 (q3 = 1, r3 = 3)
9 = 3 3 + 0. (q4 = 3 and r4 = 0)
Euclidean algorithm example, continued
I
21 = 1 12 + 9 and note that
I
0 9 < 12 and by Theorem D, that
d|9 because d|12 and d|21.
For notational purposes, let r2 = 9, and q2 = 1, where r2
stands for the second remainder and q2 stands for the second
quotient.
12 = 1 9 + 3 d|3 (q3 = 1, r3 = 3)
9 = 3 3 + 0. (q4 = 3 and r4 = 0)
Conclusion so far: d|3 in which case either d = 1 or d = 3.
Euclidean algorithm example, continued
I
21 = 1 12 + 9 and note that
I
0 9 < 12 and by Theorem D, that
d|9 because d|12 and d|21.
For notational purposes, let r2 = 9, and q2 = 1, where r2
stands for the second remainder and q2 stands for the second
quotient.
12 = 1 9 + 3 d|3 (q3 = 1, r3 = 3)
9 = 3 3 + 0. (q4 = 3 and r4 = 0)
Conclusion so far: d|3 in which case either d = 1 or d = 3.
Which is it?
The Actual Euclidean Algorithm
Recall that a (mod b) is the remainder upon dividing a by b. That
is if a = qb + r with 0 r < b then a (mod b) = r .
Algorithm Euclid
Input: a, b Z+ {0}, a b, b 6= 0.
Output: gcd(a, b)
I
I
I
If b = 0
then return a
else return Euclid(b, a (mod b))
Euclidean Algorithm Written out in Stages
I
a = q1 b + r 1
0 r1 < b
Euclidean Algorithm Written out in Stages
I
a = q1 b + r 1
0 r1 < b
b = q2 r1 + r2
0 r2 < r1
Euclidean Algorithm Written out in Stages
I
a = q1 b + r 1
0 r1 < b
b = q2 r1 + r2
0 r2 < r1
r1 = q3 r2 + r3
0 r3 < r2
Euclidean Algorithm Written out in Stages
I
a = q1 b + r 1
0 r1 < b
b = q2 r1 + r2
0 r2 < r1
r1 = q3 r2 + r3
0 r3 < r2
r2 = q4 r3 + r4
0 r4 < r3
Euclidean Algorithm Written out in Stages
I
a = q1 b + r 1
0 r1 < b
b = q2 r1 + r2
0 r2 < r1
r1 = q3 r2 + r3
0 r3 < r2
r2 = q4 r3 + r4
0 r4 < r3
..
.
Euclidean Algorithm Written out in Stages
I
a = q1 b + r 1
0 r1 < b
b = q2 r1 + r2
0 r2 < r1
r1 = q3 r2 + r3
0 r3 < r2
r2 = q4 r3 + r4
0 r4 < r3
..
.
rk3 = qk1 rk2 + rk1
0 rk1 < rk2
Euclidean Algorithm Written out in Stages
I
a = q1 b + r 1
0 r1 < b
b = q2 r1 + r2
0 r2 < r1
r1 = q3 r2 + r3
0 r3 < r2
r2 = q4 r3 + r4
0 r4 < r3
..
.
rk3 = qk1 rk2 + rk1
rk2 = qk rk1 + rk
0 rk1 < rk2
rk = 0 and we halt.
Correctness of the Euclidean Algorithm
Does the algorithm halt?
Correctness of the Euclidean Algorithm
Does the algorithm halt?
If so, does it produce the desired output, namely gcd(a, b)?
Correctness of the Euclidean Algorithm
Does the algorithm halt?
If so, does it produce the desired output, namely gcd(a, b)?
The following lemma will help answer the latter question.
Euclidean Algorithm: A helpful lemma
I
Lemma. Let a, b Z+ satisfy a = bq + r with 0 r < b (so
q = b ba c).
Then gcd(a, b) = gcd(b, r ).
Euclidean Algorithm: A helpful lemma
I
Lemma. Let a, b Z+ satisfy a = bq + r with 0 r < b (so
q = b ba c).
Then gcd(a, b) = gcd(b, r ).
Proof. Let d = gcd(a, b) and d0 = gcd(b, r ).
Euclidean Algorithm: A helpful lemma
I
Lemma. Let a, b Z+ satisfy a = bq + r with 0 r < b (so
q = b ba c).
Then gcd(a, b) = gcd(b, r ).
Proof. Let d = gcd(a, b) and d0 = gcd(b, r ).
Our goal is, therefore, to show that d0 = d.
Euclidean Algorithm: A helpful lemma
I
Lemma. Let a, b Z+ satisfy a = bq + r with 0 r < b (so
q = b ba c).
Then gcd(a, b) = gcd(b, r ).
Proof. Let d = gcd(a, b) and d0 = gcd(b, r ).
Our goal is, therefore, to show that d0 = d.
To that end, it suffices to show that d|d0 and d0 |d.
Euclidean Algorithm: A helpful lemma
I
Lemma. Let a, b Z+ satisfy a = bq + r with 0 r < b (so
q = b ba c).
Then gcd(a, b) = gcd(b, r ).
Proof. Let d = gcd(a, b) and d0 = gcd(b, r ).
Our goal is, therefore, to show that d0 = d.
To that end, it suffices to show that d|d0 and d0 |d.
Note that r = a bq, in which case d|r by Theorem D
(because d|a and d|b).
Euclidean Algorithm: A helpful lemma
I
Lemma. Let a, b Z+ satisfy a = bq + r with 0 r < b (so
q = b ba c).
Then gcd(a, b) = gcd(b, r ).
Proof. Let d = gcd(a, b) and d0 = gcd(b, r ).
Our goal is, therefore, to show that d0 = d.
To that end, it suffices to show that d|d0 and d0 |d.
Note that r = a bq, in which case d|r by Theorem D
(because d|a and d|b).
So far we have that d|r and d|b, which means that
d|gcd(b, r ) and thus d|d0 .
Proof of lemma, continued. So far we have d|d0
I
Thus it remains to show that d0 |d.
Proof of lemma, continued. So far we have d|d0
I
Thus it remains to show that d0 |d.
Here goes. By the definition of gcd we have that d0 |b and
that d0 |(a b ba cb)
Proof of lemma, continued. So far we have d|d0
I
Thus it remains to show that d0 |d.
Here goes. By the definition of gcd we have that d0 |b and
that d0 |(a b ba cb)
d|a (by Theorem D)
Proof of lemma, continued. So far we have d|d0
I
Thus it remains to show that d0 |d.
Here goes. By the definition of gcd we have that d0 |b and
that d0 |(a b ba cb)
d|a (by Theorem D)
d0 |gcd(a, b)
Proof of lemma, continued. So far we have d|d0
I
Thus it remains to show that d0 |d.
Here goes. By the definition of gcd we have that d0 |b and
that d0 |(a b ba cb)
d|a (by Theorem D)
d0 |gcd(a, b)
d0 |d.
Proof of lemma, continued. So far we have d|d0
I
Thus it remains to show that d0 |d.
Here goes. By the definition of gcd we have that d0 |b and
that d0 |(a b ba cb)
d|a (by Theorem D)
d0 |gcd(a, b)
d0 |d.
In total, we have d|d0 and d0 |d
Proof of lemma, continued. So far we have d|d0
I
Thus it remains to show that d0 |d.
Here goes. By the definition of gcd we have that d0 |b and
that d0 |(a b ba cb)
d|a (by Theorem D)
d0 |gcd(a, b)
d0 |d.
In total, we have d|d0 and d0 |d
d = d0 . That is, gcd(a, b) = gcd(b, r ). QED
Why is the Euclidean Algorithm Correct?
I
First, by the lemma, we have rk1 = gcd(a, b) because
Why is the Euclidean Algorithm Correct?
I
First, by the lemma, we have rk1 = gcd(a, b) because
gcd(a, b) = gcd(b, r1 ) = gcd(r1 , r2 ) = gcd(r2 , r3 ) = =
gcd(rk1 , rk ) = gcd(rk1 , 0) = rk1 .
Why is the Euclidean Algorithm Correct?
I
First, by the lemma, we have rk1 = gcd(a, b) because
gcd(a, b) = gcd(b, r1 ) = gcd(r1 , r2 ) = gcd(r2 , r3 ) = =
gcd(rk1 , rk ) = gcd(rk1 , 0) = rk1 .
Finally, and importantly, the algorithm halts because
r1 > r2 > r3 > is a strictly decreasing sequence of
non-negative integers, which means that, eventually, rk = 0
for some k 1.
Why is the Euclidean Algorithm Correct?
I
First, by the lemma, we have rk1 = gcd(a, b) because
gcd(a, b) = gcd(b, r1 ) = gcd(r1 , r2 ) = gcd(r2 , r3 ) = =
gcd(rk1 , rk ) = gcd(rk1 , 0) = rk1 .
Finally, and importantly, the algorithm halts because
r1 > r2 > r3 > is a strictly decreasing sequence of
non-negative integers, which means that, eventually, rk = 0
for some k 1.
In particular, the last non-zero remainder, namely rk1 , is
exactly gcd(a, b).
Euclidean Algorithm and its relation to the Fibonacci
Numbers
Optional Material
Lemma 31.10 in Introduction to Algorithms by Cormen,
Lieserson, Rivest, and Stein: number of recursive calls
I
Lemma 31.10 in CLRS If a, b 1 are integers and
Euclid(a, b) performs n 1 recursive calls, then a Fn+2 and
b Fn+1 , where Fi is the ith Fibonacci number.
Lemma 31.10 in Introduction to Algorithms by Cormen,
Lieserson, Rivest, and Stein: number of recursive calls
I
Lemma 31.10 in CLRS If a, b 1 are integers and
Euclid(a, b) performs n 1 recursive calls, then a Fn+2 and
b Fn+1 , where Fi is the ith Fibonacci number.
Proof by induction on n.
Lemma 31.10 in Introduction to Algorithms by Cormen,
Lieserson, Rivest, and Stein: number of recursive calls
I
Lemma 31.10 in CLRS If a, b 1 are integers and
Euclid(a, b) performs n 1 recursive calls, then a Fn+2 and
b Fn+1 , where Fi is the ith Fibonacci number.
Proof by induction on n.
The statement P(n) is exactly the statement of the lemma.
Lemma 31.10 in Introduction to Algorithms by Cormen,
Lieserson, Rivest, and Stein: number of recursive calls
I
Lemma 31.10 in CLRS If a, b 1 are integers and
Euclid(a, b) performs n 1 recursive calls, then a Fn+2 and
b Fn+1 , where Fi is the ith Fibonacci number.
Proof by induction on n.
The statement P(n) is exactly the statement of the lemma.
Base Case. n = 1. Since one recursion occurs we have
b > 0. That is, b 1 = F2 .
Lemma 31.10 in Introduction to Algorithms by Cormen,
Lieserson, Rivest, and Stein: number of recursive calls
I
Lemma 31.10 in CLRS If a, b 1 are integers and
Euclid(a, b) performs n 1 recursive calls, then a Fn+2 and
b Fn+1 , where Fi is the ith Fibonacci number.
Proof by induction on n.
The statement P(n) is exactly the statement of the lemma.
Base Case. n = 1. Since one recursion occurs we have
b > 0. That is, b 1 = F2 .
By assumption a > b a 2 = F3 .
Lemma 31.10 in Introduction to Algorithms by Cormen,
Lieserson, Rivest, and Stein: number of recursive calls
I
Lemma 31.10 in CLRS If a, b 1 are integers and
Euclid(a, b) performs n 1 recursive calls, then a Fn+2 and
b Fn+1 , where Fi is the ith Fibonacci number.
Proof by induction on n.
The statement P(n) is exactly the statement of the lemma.
Base Case. n = 1. Since one recursion occurs we have
b > 0. That is, b 1 = F2 .
By assumption a > b a 2 = F3 .
Also, since b > a (mod b) (why?) in each recursive call
we have a > b.
Euclid(
a, b)
Proof of lemma 31.10, continued.
I
Induction Hypothesis. Assume the lemma is true if k 1
recursive calls have made (i.e., assume P(k 1) is true).
Proof of lemma 31.10, continued.
I
Induction Hypothesis. Assume the lemma is true if k 1
recursive calls have made (i.e., assume P(k 1) is true).
Inductive Step. We must prove the lemma is true when k
recursive calls have been made (i.e., verify P(k) is true).
Proof of lemma 31.10, continued.
I
Induction Hypothesis. Assume the lemma is true if k 1
recursive calls have made (i.e., assume P(k 1) is true).
Inductive Step. We must prove the lemma is true when k
recursive calls have been made (i.e., verify P(k) is true).
To that end, we have k > 0 and b > 0.
Proof of lemma 31.10, continued.
I
Induction Hypothesis. Assume the lemma is true if k 1
recursive calls have made (i.e., assume P(k 1) is true).
Inductive Step. We must prove the lemma is true when k
recursive calls have been made (i.e., verify P(k) is true).
To that end, we have k > 0 and b > 0.
Assume Euclid(a, b) makes k recursive calls.
Proof of lemma 31.10, continued.
I
Induction Hypothesis. Assume the lemma is true if k 1
recursive calls have made (i.e., assume P(k 1) is true).
Inductive Step. We must prove the lemma is true when k
recursive calls have been made (i.e., verify P(k) is true).
To that end, we have k > 0 and b > 0.
Assume Euclid(a, b) makes k recursive calls.
Euclid(a, b) first returns Euclid(b, a (mod b)), which makes
k 1 recursive calls.
Proof of lemma 31.10, continued.
I
Induction Hypothesis. Assume the lemma is true if k 1
recursive calls have made (i.e., assume P(k 1) is true).
Inductive Step. We must prove the lemma is true when k
recursive calls have been made (i.e., verify P(k) is true).
To that end, we have k > 0 and b > 0.
Assume Euclid(a, b) makes k recursive calls.
Euclid(a, b) first returns Euclid(b, a (mod b)), which makes
k 1 recursive calls.
By the induction hypothesis, we have b Fk+1 and a
(mod b) Fk .
Proof of lemma 31.10, continued.
I
Induction Hypothesis. Assume the lemma is true if k 1
recursive calls have made (i.e., assume P(k 1) is true).
Inductive Step. We must prove the lemma is true when k
recursive calls have been made (i.e., verify P(k) is true).
To that end, we have k > 0 and b > 0.
Assume Euclid(a, b) makes k recursive calls.
Euclid(a, b) first returns Euclid(b, a (mod b)), which makes
k 1 recursive calls.
By the induction hypothesis, we have b Fk+1 and a
(mod b) Fk .
It remains to show that a Fk+2 .
Proof of lemma 31.10, continued. Must show a Fk+2 .
Note that b + a (mod b)
Proof of lemma 31.10, continued. Must show a Fk+2 .
Note that b + a (mod b)
=b+r
Proof of lemma 31.10, continued. Must show a Fk+2 .
Note that b + a (mod b)
=b+r
= b + (a b ba cb)
Proof of lemma 31.10, continued. Must show a Fk+2 .
Note that b + a (mod b)
=b+r
= b + (a b ba cb)
Proof of lemma 31.10, continued. Must show a Fk+2 .
Note that b + a (mod b)
=b+r
= b + (a b ba cb)
because b ba c > 1.
Proof of lemma 31.10, continued. Must show a Fk+2 .
Thus we have that a b + a (mod b)
Proof of lemma 31.10, continued. Must show a Fk+2 .
Thus we have that a b + a (mod b)
Fk+1 + Fk
Proof of lemma 31.10, continued. Must show a Fk+2 .
Thus we have that a b + a (mod b)
Fk+1 + Fk
= Fk+2 , as desired.
Proof of lemma 31.10, continued. Must show a Fk+2 .
Thus we have that a b + a (mod b)
Fk+1 + Fk
= Fk+2 , as desired.
Conclusion. If Euclid(a, b) makes n recursive calls then
a Fn+2 and b Fn+1 .
Proof of lemma 31.10, continued. Must show a Fk+2 .
Thus we have that a b + a (mod b)
Fk+1 + Fk
= Fk+2 , as desired.
Conclusion. If Euclid(a, b) makes n recursive calls then
a Fn+2 and b Fn+1 .
QED
Direct Consequence of Lemma 31.10
Theorem 31.11. If a > b 1 and b < Fn+1 then
Euclid(a, b) makes at least n 1 recursive calls.
Direct Consequence of Lemma 31.10
Theorem 31.11. If a > b 1 and b < Fn+1 then
Euclid(a, b) makes at least n 1 recursive calls.
This theorem is best possible:
Direct Consequence of Lemma 31.10
Theorem 31.11. If a > b 1 and b < Fn+1 then
Euclid(a, b) makes at least n 1 recursive calls.
This theorem is best possible:
To see why, let a = Fn+2 and b = Fn+1 then Euclid(a, b) will
perform as follows:
Best possible theorem
I
Recall that a = Fn+2 and b = Fn+1 .
Best possible theorem
I
Recall that a = Fn+2 and b = Fn+1 .
Then gcd(Fn+1 , Fn ) = gcd(Fn , Fn1 ) = = gcd(F1 , F0 ) =
gcd(1, 0) = 1.
Best possible theorem
I
Recall that a = Fn+2 and b = Fn+1 .
Then gcd(Fn+1 , Fn ) = gcd(Fn , Fn1 ) = = gcd(F1 , F0 ) =
gcd(1, 0) = 1.
Thus n recursive calls will be made the theorem is best
possible.
Best possible theorem
I
Recall that a = Fn+2 and b = Fn+1 .
Then gcd(Fn+1 , Fn ) = gcd(Fn , Fn1 ) = = gcd(F1 , F0 ) =
gcd(1, 0) = 1.
Thus n recursive calls will be made the theorem is best
possible.
Finally, given that Fn
n
5 ,
where =
1+ 5
2 ,
we see that
Best possible theorem
I
Recall that a = Fn+2 and b = Fn+1 .
Then gcd(Fn+1 , Fn ) = gcd(Fn , Fn1 ) = = gcd(F1 , F0 ) =
gcd(1, 0) = 1.
Thus n recursive calls will be made the theorem is best
possible.
Finally, given that Fn
Euclid(a, b) makes C log b recursive calls.
n
5 ,
where =
1+ 5
2 ,
we see that
Best possible theorem
I
Recall that a = Fn+2 and b = Fn+1 .
Then gcd(Fn+1 , Fn ) = gcd(Fn , Fn1 ) = = gcd(F1 , F0 ) =
gcd(1, 0) = 1.
Thus n recursive calls will be made the theorem is best
possible.
Finally, given that Fn
Euclid(a, b) makes C log b recursive calls.
Moral of the story: recursion is not always bad!
n
5 ,
where =
1+ 5
2 ,
we see that
