CENTRAL ASIAN JOURNAL OF INNOVATIONS ON TOURISM

MANAGEMENT AND FINANCE

Volume: 04 Issue: 02 | 2023 ISSN: 2660-454X

https://cajitmf.centralasianstudies.org

The History of Euclidean Algorithm

Abstract: The Euclidean Algorithm is one of the oldest

1
Yuldoshev Mansur Najmiddin ugli numerical algorithms still in use today. Attributed to ancient
Greek mathematician Euclid in his book “Elements” written
approximately 300 BC, the algorithm serves as an effective
Received 16th Dec 2022, method for finding the greatest common divisor of two whole
Accepted 19th Jan 2023,
Online 28th Feb 2023
numbers. This article discusses about Euclidean Algorithm.

1
Key words: Euclidean Algorithm, math sums, irrational
Academic Lyceum of Tashkent State
numbers, natural numbers, etc.
University of Economics lead math science
teacher
[email protected]

The greatest common divisor (GCD) of two whole numbers is the largest natural number that divides
evenly into both without a remainder. We‟ll begin with the formal definition and then work an example.
If mathematical notation makes your eyes glaze over, hang in there! It‟s actually pretty straightforward
when you see the example. In the initial setup, the values for a-0 and b are the two values we want to find
the GCD of, a-o being the larger of the two. The goal of each step is to find the quotient q and remainder
r that makes the equation true. The Euclidean Algorithm is a k-step iterative process that ends when the
remainder is zero. (In other words, you keep going until there‟s no remainder.) The GCD will be the last
non-zero remainder. Euclidean algorithm, procedure for finding the greatest common divisor (GCD) of
two numbers, described by the Greek mathematician Euclid in his Elements (c. 300 BC). The method is
computationally efficient and, with minor modifications, is still used by computers.
The algorithm involves successively dividing and calculating remainders; it is best illustrated by
example. For instance, to find the GCD of 56 and 12, first divide 56 by 12 and note that the quotient is 4
and the remainder is 8. This can be expressed as 56 = 4 × 12 + 8. Now take the divisor (12), divide it by
the remainder (8), and write the result as 12 = 1 × 8 + 4. Continuing in this manner, take the previous
divisor (8), divide it by the previous remainder (4), and write the result as 8 = 2 × 4 + 0. Since the
remainder is now 0, the process has finished and the last nonzero remainder, in this case 4, is the GCD.
The Euclidean algorithm is useful for reducing a common fraction to lowest terms. For example, the
algorithm will show that the GCD of 765 and 714 is 51, and therefore 765/714 = 15/14. It also has a
number of uses in more advanced mathematics. For example, it is the basic tool used to find integer
solutions to linear equations ax + by = c, where a, b, and c are integers. The algorithm also provides, as

140 Published by “ CENTRAL ASIAN STUDIES" http://www.centralasianstudies.org

Copyright (c) 2023 Author (s). This is an open-access article distributed under the terms of Creative Commons
Attribution License (CC BY).To view a copy of this license, visit https://creativecommons.org/licenses/by/4.0/
CAJITMF Volume: 04 Issue: 02 | Feb 2023

the successive quotients obtained from the division process, the integers a, b, …, f needed for the
expansion of a fraction p/q as a continued fraction:

The Euclidean Algorithm is truly fundamental to many other algorithms throughout the history of
computer science and will definitely be used again later. At least to me, it's amazing how such an ancient
algorithm can still have modern use and appeal. That said, there are still other algorithms out there that
can find the greatest common divisor of two numbers that are arguably better in certain cases than the
Euclidean algorithm, but the fact that we are discussing Euclid two millennia after his death shows how
timeless and universal mathematics truly is. I think that's pretty cool. Computer science is (almost by
definition) a science about computers -- a device first conceptualized in the 1800's. Computers have
become so revolutionary, that it is difficult to think of our lives today without them. That said, algorithms
are much older and have existed in the world for millennia. Incredibly, a few of the algorithms created
before the Common Era (AD) are still in use today. One such algorithm was first described in Euclid's
Elements (~ 300 BC) and has come to be known as the Euclidean Algorithm. More than two millennia
ago Euclid (circa 300 BCE) described a method for computing the "greatest common measure" of two
"numbers", and today we name our modern iterative algorithm for calculating the greatest common
divisor of two numbers after him. Here we introduce and provide for instructors a student project based
on Euclid's original source, designed for a course in introductory discrete mathematics or computer
science. The similarities and differences between our modern algorithms and what Euclid presented and
proved are extremely fertile ground for initial student learning about algorithms and proofs. For instance,
as shown below, Euclid adopted a highly geometric description of his numbers as lengths. Euclid's
presentation also naturally sets the stage, if desired, to extend the project by comparing and contrasting
with a modern day recursive, as opposed to iterative, formulation of the algorithm, as it is often presented
to computer science students. And the highly contrasting proofs of correctness in these two very different
settings can be explored.
The project can be used to provide a first introduction to the notion of "computation method" or
"algorithm" and to explore concepts like iteration and the efficacy of mathematical induction as a method
of proof, thereby covering a number of typical course topics. The project can even be used to introduce
induction. With this project students can develop their skill at creating proofs in a highly authentic and
motivated context, but just as importantly they can experience the evolution of what is accepted as a valid
proof or a well-described algorithm. Students will learn that the method presented by Euclid to compute
the greatest common divisor and the proof of its correctness that he provided would not be formally
accepted today. Students will also experience, however, that Euclid was somehow able to convey the
ideas behind his method and proof in such a way that they can reform Euclid's writing into a modern
algorithm and proof of correctness. In this way, the project provides students not only with a strong sense
of connection to the past, but also serious practice with subtle issues about the nature of adequate
mathematical formulation and proof today. Students can work productively in groups on this project, with
group or individual writeups. They will need substantial guidance with the optional exercises near the end
of the project, which formalize the algorithm in wholly modern terms and prove correctness using finite
induction. In any case, the instructor should always work through all details before assigning any student
work. The issue of "unit" versus "number" will provide grist for substantial class discussion and careful
attention to detail in interpreting Euclid's analysis of his algorithm. It seems clear that by "unit" Euclid
meant what we today call the number "one", but that to him it was not a number. Why this was the case
for Euclid, and how it played out in his writings, is rich material for critical consideration when studying
Euclid.
141 Published by “ CENTRAL ASIAN STUDIES" http://www.centralasianstudies.org
Copyright (c) 2023 Author (s). This is an open-access article distributed under the terms of Creative Commons
Attribution License (CC BY).To view a copy of this license, visit https://creativecommons.org/licenses/by/4.0/
CAJITMF Volume: 04 Issue: 02 | Feb 2023

In mathematics, the Euclidean algorithm,[note 1] or Euclid's algorithm, is an efficient method for

computing the greatest common divisor (GCD) of two integers (numbers), the largest number that divides
them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first
described it in his Elements (c. 300 BC). It is an example of an algorithm, a step-by-step procedure for
performing a calculation according to well-defined rules, and is one of the oldest algorithms in common
use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic
and cryptographic calculations. Euclid's method for finding the greatest common divisor (GCD) of two
starting lengths BA and DC, both defined to be multiples of a common "unit" length. The length DC
being shorter, it is used to "measure" BA, but only once because remainder EA is less than DC. EA now
measures (twice) the shorter length DC, with remainder FC shorter than EA. Then FC measures (three
times) length EA. Because there is no remainder, the process ends with FC being the GCD. On the right
Nicomachus's example with numbers 49 and 21 resulting in their GCD of 7 (derived from Heath
1908:300).
The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does
not change if the larger number is replaced by its difference with the smaller number. For example, 21 is
the GCD of 252 and 105 (as 252 = 21 × 12 and 105 = 21 × 5), and the same number 21 is also the GCD
of 105 and 252 − 105 = 147. Since this replacement reduces the larger of the two numbers, repeating this
process gives successively smaller pairs of numbers until the two numbers become equal. When that
occurs, they are the GCD of the original two numbers. By reversing the steps or using the extended
Euclidean algorithm, the GCD can be expressed as a linear combination of the two original numbers, that
is the sum of the two numbers, each multiplied by an integer (for example, 21 = 5 × 105 + (−2) × 252.
The fact that the GCD can always be expressed in this way is known as Bézout's identity.
References:
1. A. A. A ‟zamov, В. K. Xaydarov. M atem atika sayyorasi. , , 0 „qituvchi“ , Т., 1993.
2. T. A. Azlarov, M. A. Mirzaahmedov, D. 0. Otaqo„ziyev, M. A. Sobirov, S. T. T o„lagcinov.
Matematikadan qoMlanma (maktab o „qituvchilari uchun q o „llanma). 2-qism. 0 „qituvchi, Т., 1990.
3. S. I. Afonina. M atem atika va go „zallik. , , 0 „qituvchi“ , Т., 1987.
4. Sh. A. Ayupov, В. B. Rixsiyev, O. Sh. Qo'chqomv. Matematika olimpiadalari masalalari. I, II
qismlar, ,,F A N “ Т., 2004.
5. В. Г. Болтянский, В. А. Ефремович. Наглядная топология. Н аука, М., 1982.
6. С.Г.Гиндикин. Рассказы о ф изиках и математиках. Наука, М., 1985.

142 Published by “ CENTRAL ASIAN STUDIES" http://www.centralasianstudies.org

Copyright (c) 2023 Author (s). This is an open-access article distributed under the terms of Creative Commons
Attribution License (CC BY).To view a copy of this license, visit https://creativecommons.org/licenses/by/4.0/