| Objectives:
1) Understand
the Euclidean Algorithm to determine the greatest common divisor of
2 integers.
2) Learn how to
program the Euclidean Algorithm.
|
|
The Euclidean Algorithm
We encountered that some ciphers require the knowledge of the greatest common
divisor of two integers, others require the usage of two integers with a 1 as a
common divisor. On this page, I will demonstrate to you how the Euclidean Algorithm
can be used in both instances. It is named after Euclid since he was the first
person to describe this mathematical procedure. It is easy to understand as you
will see below and it is the most efficient method to compute the greatest
common divisor (in brief "gcd"). Even the gcd of i.e. two 9-digit
numbers can be found quickly.
|
|
Let's recall some
school terminology: When dividing one integer by another (nonzero) integer we
get an integer quotient (the "answer") plus a remainder
(generally a rational number). For instance, 13/5 = 2 ("the
quotient") + 3/5 ("the remainder").
We can rewrite this division in terms of integers as follows:
13 = 2 * 5 + 3.
This expression is obtained from the one above it through
multiplication by the divisor 5.
We refer to this way of writing a division of integers as the Division
Algorithm for Integers. More formally stated:
If a and b are positive integers, there exist unique non-negative
integers q and r so that a = qb + r , where 0 <= r
< b.
where
q is called the quotient and r the remainder.
The greatest common divisor
of integers a and b, denoted by gcd(a,b), is the largest integer that
divides (without remainder) both a and b. So, for example: |
| gcd(15, 5) =5, |
gcd(9,3) =3, |
gcd(19, 9) =1, |
gcd(81, 57) =3. |
|
|
The gcd of two integers can be found by
repeated application of the division algorithm, this is known as the Euclidean Algorithm.
I.e.: To find the gcd of 81 and 57 by the Euclidean Algorithm, we
proceed as follows: 81 = 1 * 57 + 24
57 = 2 * 24 + 9
24 = 2 * 9 + 6
9 = 1 * 6 + 3
6 = 2 * 3 + 0.
We repeatedly
divide the divisor by the remainder until the remainder is 0. The
gcd is the last non-zero remainder in this algorithm, 3 in
our example.
Exercise
1:
Find
the greatest common divisor of 26 and 21 using the Euclidean Algorithm by
hand. 1 Exercise
2:
Find
the greatest common divisor of 81 and 54 using the Euclidean
Algorithm by hand. 27 Exercise
3:
Find the greatest
common divisor of 81 and 51 using the Euclidean Algorithm by hand.
3 Exercise
4:
Find the
greatest common divisor of 3456 and 1720 using the Euclidean Algorithm by hand.
8 Afterwards,
verify your computations below.
Implementation of the
Euclidean Algorithm
|
| The Euclidean Algorithm should be performed by
a computer. It is very easy to implement and it yields the answer
quickly. If you happened to study Computer Sciences in College you are almost
guaranteed to encounter this algorithm in one of your first classes. The
reason: Only a few lines of code are needed to implement a very
efficient algorithm. Here they are:
while
(r != 0){
r = a % b;
a = b;
b = r;
} |
a = larger
integer,
b = small integer,
r = remainder. |
The gcd is found as the
value of a when r is 0. (What is the value of b at that time?) I used
this code below so that you
can compute the gcd of any two integers a and b. Additionally, you can observe
the steps involved that lead to the final answer. Thus, enter the two integers
a and b followed by hitting the "Compute GCD" button to scrutinize
the computation process until the gcd is found.
|
| Enter a=
- the larger integer. |
| Enter b=
- the smaller integer (the modulus in some cases). |
|
|
|
The GCD can be read off as the remainder in the 2nd
to last line:
To observe the
efficiency of the algorithm compute i.e. GCD(81543254,57435333).
|
|
|
|
Euclid of Alexandria (325-265 BC)
was the most prominent
Mathematician at his time. He
summarized his discoveries in "The
Elements". Here is an excerpt:
1. There are infinitely many primes.
2. Euclidean Geometry.
3. Euclidean Algorithm.
Find
all information on Euclid here
|
Related web sources:
Cut-the-knot.com
(Play the Euclid game here)
Encarta.com
Glossary
PBS
Online
Introduction
to Cryptography
Enigma
and the Codebreakers
Enigma
History
Enigma
Emulator
|