Art Two: Euclidean Division Algorithm The Euclidean division algorithm is a method for finding the highest common factor (also called the greatest
common divisor) of two numbers. It is a method that can be performed by hand or programmed into a
computer to quickly find the result. Euclid, the famous Greek mathematician, first published the algorithm in
his well-known books titled Elements in about 300 BCE. The algorithm is used today in many mathematical
situations. It is also an important part of today's public key encryption method that is used to code and
decipher electronic information in the world of commerce
In simple terms this is how the algorithm works:
. Let the two numbers be a and b where a >b.
• Let ca-b.
• Let the new a and b be the smallest pair from the previous a, b and c. Make a > b.
• Repeat the above two steps until a = b. The HCF is the value of a (or b) at this point,
• If a - b = 1 then the HCF = 1.
Prove
1. Use the Euclidean division algorithm to find the HCF for six different pairs of numbers.
(Hint: The pair of numbers you choose should include larger and smaller numbers)