Mathematics
Euclidean Algorithm
The Euclidean Algorithm is a method for finding the greatest common divisor (GCD) of two integers. It involves repeatedly dividing the larger number by the smaller number and taking the remainder until the remainder is zero. The GCD is then the last non-zero remainder.
Written by Perlego with AI-assistance
Related key terms
1 of 5
10 Key excerpts on "Euclidean Algorithm"
No longer available |Learn more- (Author)
- 2014(Publication Date)
- Learning Press(Publisher)
This led to modern abstract algebraic notions such as Euclidean domains. The Euclidean Algorithm has been generalized further to other mathematical structures, such as knots and multivariate polynomials. The Euclidean Algorithm has many theoretical and practical applications. It may be used to generate almost all the most important traditional musical rhythms used in different cultures throughout the world. It is a key element of the RSA algorithm, a public-key encryption method widely used in electronic commerce. It is used to solve Diophantine equations, such as finding numbers that satisfy multiple congruences (Chinese remainder theorem) or multiplicative inverses of a finite field. The Euclidean Algorithm can also be used in constructing continued fractions, in the Sturm chain method for finding real roots of a polynomial, and in several modern integer factorization algorithms. Finally, it is a basic tool for proving theorems in modern number theory, such as Lagrange's four-square theorem and the fundamental theorem of arithmetic (unique factorization). Euclid's algorithm computes the GCD of large numbers efficiently, because it never requires more steps than five times the number of digits (base 10) of the smaller integer. This was proved by Gabriel Lamé in 1844, and marks the beginning of computational complexity theory. Methods for improving the algorithm's efficiency were developed in the 20th century. ________________________ WORLD TECHNOLOGIES ________________________ Background Greatest common divisor The Euclidean Algorithm calculates the greatest common divisor (GCD) of two natural numbers a and b . The greatest common divisor g is the largest natural number that divides both a and b without leaving a remainder. Synonyms for the GCD include the greatest common factor (GCF), the highest common factor (HCF), and the greatest common measure (GCM).
No longer available |Learn more- (Author)
- 2014(Publication Date)
- Orange Apple(Publisher)
________________________ WORLD TECHNOLOGIES ________________________ Chapter- 6 Euclidean Algorithm Image of the Euclidean Algorithm for 252 and 105. The crossbars represent multiples of 21, the greatest common divisor (GCD). In each step, the smaller number is subtracted from the larger number, until one number is reduced to zero. The remaining number is the GCD. In mathematics, the Euclidean Algorithm (also called Euclid's algorithm ) is an efficient method for computing the greatest common divisor (GCD), also known as the greatest common factor (GCF) or highest common factor (HCF). It is named after the Greek mathematician Euclid, who described it in Books VII and X of his Elements . ________________________ WORLD TECHNOLOGIES ________________________ The GCD of two numbers is the largest number that divides both of them without leaving a remainder. The Euclidean Algorithm is based on the principle that the greatest common divisor of two numbers does not change if the smaller number is subtracted from the larger number. For example, 21 is the GCD of 252 and 105 (252 = 21 × 12; 105 = 21 × 5); since 252 − 105 = 147, the GCD of 147 and 105 is also 21. Since the larger of the two numbers is reduced, repeating this process gives successively smaller numbers until one of them is zero. When that occurs, the GCD is the remaining nonzero number. By reversing the steps in the Euclidean Algorithm, the GCD can be expressed as a sum of the two original numbers each multiplied by a positive or negative integer, e.g., 21 = 5 × 105 + (−2) × 252. This important property is known as Bézout's identity. The earliest surviving description of the Euclidean Algorithm is in Euclid's Elements (c. 300 BC), making it one of the oldest numerical algorithms still in common use.
eBook - PDFElements of Mathematics
From Euclid to Gödel
- John Stillwell(Author)
- 2016(Publication Date)
- Princeton University Press(Publisher)
This simple fact is the basis of an efficient algorithm for finding the greatest common divisor. It is called the Euclidean Algorithm after Euclid, who described it over 2000 years ago in the Elements , Book VII, Proposition 2. In Euclid’s words, one “continually subtracts the lesser number from the greater.” More formally, one computes a sequence of pairs of numbers. Arithmetic • 37 Euclidean Algorithm. Starting with a given pair a , b , where a > b , each new pair consists of the smaller member of the previous pair, and the difference of the previous pair. The algorithm terminates with a pair of equal numbers, each of which is the greatest common divisor of a and b . For example, if we start with the pair a = 13, b = 8, the algorithm leads to the pair (1 , 1), as we found in section 1.2, so 1 is the greatest common divisor of 13 and 8. The main reason that the Euclidean Algorithm works is the fact noted above: that greatest common divisor of a and b is also a divisor of a − b . If we denote the greatest common divisor by gcd, then gcd( a , b ) = gcd( b , a − b ) and in the above example we have gcd(13 , 8) = gcd(8 , 5) = gcd(5 , 3) = gcd(3 , 2) = gcd(2 , 1) = gcd(1 , 1) = 1 . (Notice that, when we start with the consecutive Fibonacci numbers 13 and 8, subtraction gives all the preceding Fibonacci numbers, ending inevitably at the number 1. It is the same with any pair of consecutive Fibonacci numbers, so the gcd of any such pair is 1.) A secondary reason, also important, is that the algorithm contin-ually produces smaller numbers, and hence it terminates (necessarily with equal numbers) because positive integers cannot decrease forever . This “no infinite descent” principle is obvious, and Euclid often used it, but it is nevertheless profound. It is the first expression of proof by induction , which underlies all of number theory, as we will see in section 9.4.
eBook - PDF- James J. Tattersall(Author)
- 2005(Publication Date)
- Cambridge University Press(Publisher)
2.3 The Euclidean Algorithm A method to determine the greatest common divisor of two integers, known as the Euclidean Algorithm, appears in Book VII of Euclid’s Elements. It is one of the few numerical procedures contained in the Elements. It is the oldest algorithm that has survived to the present day. The method appears in India in the late fifth century Hindu astronomical work Aryabhatiya by Aryabhata. Aryabhata’s work contains no equations. It includes 50 verses devoted to the study of eclipses, 33 to arithmetic, and 25 to time reckoning and planetary motion. Aryabhata called his technique the ‘pulverizer’ and used it to determine integer solutions x, y to the equation ax by ¼ c, where a, b and c are integers. We discuss Aryabhata’s method in Chapter 5. In 1624, Bachet included the algorithm in the second edition of his Proble `mes plaisants et de ´lectables. It was the first numerical exposition of the method to appear in Europe. The Euclidean Algorithm, is based on repeated use of the division algorithm. Given two integers a and b where, say a > b . 0, determine the sequences q 1 , q 2 , . . . , q nþ1 and r 1 , r 2 . . . , r nþ1 of quotients and remainders in the following manner. a ¼ bq 1 þ r 1 , where 0 < r 1 , b: b ¼ r 1 q 2 þ r 2 , where 0 < r 2 , r 1 : r 1 ¼ r 2 q 3 þ r 3 , where 0 < r 3 , r 2 : . . . r n2 ¼ r n1 q n þ r n , where 0 < r n , r n1 : r n1 ¼ r n q nþ1 : Suppose r n 6¼ 0. Since b . r 1 . r 2 > 0, r 1 , r 2 , . . . , r nþ1 is a de- creasing sequence of nonnegative integers and must eventually terminate with a zero remainder, say r nþ1 ¼ 0. From the last equation in the Euclidean Algorithm, we have that r n divides r n1 and from the penultimate equation it follows that r n divides r n2 . Continuing this process we find that r n divides both a and b. Thus, r n is a common divisor of a and b. Suppose that e is any positive integer which divides both a and b. From the 70 Divisibility
eBook - PDF- Andrew Granville(Author)
- 2019(Publication Date)
- American Mathematical Society(Publisher)
Chapter 1 The Euclidean Algorithm 1.1. Finding the gcd Most readers will know the Euclidean Algorithm, used to find the greatest common divisor (gcd) of two given integers. For example, to determine the greatest common divisor of 85 and 48, we begin by subtracting the smaller from the larger, 48 from 85, to obtain 85 − 48 = 37. Now gcd(85 , 48) = gcd(48 , 37), because the common divisors of 48 and 37 are precisely the same as those of 85 and 48, and so we apply the algorithm again to the pair 48 and 37. So we subtract the smaller from the larger to obtain 48 − 37 = 11, so that gcd(48 , 37) = gcd(37 , 11). Next we should subtract 11 from 37, but then we would only do so again, and a third time, so let’s do all that in one go and take 37 − 3 × 11 = 4, to obtain gcd(37 , 11) = gcd(11 , 4). Similarly we take 11 − 2 × 4 = 3, and then 4 − 3 = 1, so that the gcd of 85 and 48 is 1. This is the Euclidean Algorithm that you might already have seen, 1 but did you ever prove that it really works? To do so, we will first carefully define terms that we have implicitly used in the above paragraph, perhaps mathematical terms that you have used for years (such as “divides”, “quotient”, and “remainder”) without a formal definition. This may seem pedantic but the goal is to make sure that the rules of basic arithmetic are really established on a sound footing. Let a and b be given integers. We say that a is divisible by b , or that b divides a , 2 if there exists an integer q such that a = qb . For convenience we write “ b | a ”. 3 , 4 We now set an exercise for the reader to check that the definition allows one to manipulate the notion of division in several familiar ways. Exercise 1.1.1. In this question, and throughout, we assume that a , b , and c are integers. (a) Prove that if b divides a , then either a = 0 or | a | ≥ | b | . 1 There will be a formal discussion of the Euclidean Algorithm in appendix 1A.
eBook - PDFApplied Algebra
Codes, Ciphers and Discrete Algorithms, Second Edition
- Darel W. Hardy, Fred Richman, Carol L. Walker(Authors)
- 2009(Publication Date)
- Chapman and Hall/CRC(Publisher)
Chapter 3 Euclidean Algorithm The Euclidean Algorithm was stated by Euclid in his Elements over 2000 years ago. It is still the most efficient way to find the greatest common divisor of two integers. Before investigating the Euclidean Algorithm, we take a look at the mod function. This function can be used to define modular arithmetic, which is used extensively in applied algebra. 3.1 The Mod Function When you look at an analog clock, you can’t tell how many times the hour hand has gone around the clock—you only see where the hand is currently pointing. The clock uses mod 12 arithmetic. If it is now 9:00, then 5 hours later it will be 2:00. Thus, on a clock, 9 + 5 = 2. We describe this by saying that 9 + 5 mod 12 = 2 We also do this for integers other than 12. Definition 3.1 (The mod function) If n and m are integers with m > 0 , then we define n mod m = n − n/m m If we rearrange this equation, we see that each integer n can be written as an integer multiple of m plus a remainder which is one of the numbers 0 , 1 , 2 , . . ., m − 1: n = n/m m + n mod m We say that when we divide m into n , we get a quotient q = n/m and a remainder r = n mod m . Do you see why the n mod m is one of the numbers 0 , 1 , 2 , . . ., m − 1? 39 40 CHAPTER 3. Euclidean Algorithm The computation of the quotient, n/m , and remainder, n mod m , is the division algorithm . We can write the quotient in terms of the remainder n/m = n − n mod m m so if a programming language implements the function n mod m , we can compute the quotient n/m without having to form the floating point number n/m . On the other hand, the definition of n mod m given above is easy to execute on any hand calculator where everything floats. Example 3.2 Let n = 23 and m = 7. Then 23 mod 7 = 23 − 23 / 7 7 = 23 − 3 · 7 = 23 − 21 = 2 On a calculator, you would form 23 / 7 = 3 . 285 . . . , drop the decimal part to get 3, multiply that by 7 and subtract from 23 to get 2.
eBook - PDF- Thomas Q. Sibley(Author)
- 2015(Publication Date)
- Wiley(Publisher)
However, that is not part of the definition; rather it is a theorem, and so will need to be proven. 1.5 INTRODUCTION TO NUMBER THEORY 45 Remainders So far, we have considered when a number divides another. Now, 7 doesn’t divide 33; indeed, dividing 33 by 7 gives a quotient of 4 with a remainder of 5, since 33 = 4 · 7 + 5. The generalization of this idea of remainders is still called the Division Algorithm, even though its statement isn’t an algorithm in the computer science meaning. In computer science an algorithm is a step-by-step process, as Example 5 illustrates. THEOREM: THE DIVISION ALGORITHM. For any integer z and any natural number n there are unique integers q and r such that z = qn + r and 0 ≤ r < n. (The proof appears in Section 2.4.) EXAMPLE 4 For the remainder of z = −53 divided by n = 7, it may seem natural to start with 53 = 7 · 7 + 4 and so write −53 = ( − 7) · 7 − 4. However, the remainder can’t be negative. Instead, we write −53 = ( − 8) · 7 + 3. ♦ EXAMPLE 5 Use the Division Algorithm to find the greatest common divisor of 10,800 and 1764. Euclid described the method of this example, now called the Euclidean Algorithm, an algorithm in the modern sense. Solution The first time, let z = z 1 be the bigger of the two numbers (10,800) and n = n 1 the smaller (1764). From the Division Algorithm, 10, 800 = 6 · 1764 + 216. To continue, we use the divisor n 1 = 1764 as z 2 and the remainder r 1 = 216 as n 2 . Then 1764 = 8 · 216 + 36, and the third round gives 216 = 6 · 36 + 0. Thus, the last nonzero remainder, 36, divides 216 and in turn it divides 1764 and 10,800, making 36 a common divisor. In fact, 36 = gcd(10, 800, 1764). Euclid showed that this approach always produces the greatest common divisor. This repeated division seems an unenlightening way to find the gcd of two numbers, compared with the prime factorizations in Example 3.
eBook - PDFAbstract Algebra
A Comprehensive Introduction
- John W. Lawrence, Frank A. Zorzitto(Authors)
- 2021(Publication Date)
- Cambridge University Press(Publisher)
The choice gcd(0, 0) = 0 is further justified by the fact that 0 is the only divisor of 0, which is also divisible by all other divisors of 0. The Euclidean Algorithm For pairs of small integers, their greatest common divisor can be seen by inspection. For instance, gcd(42, 30) = 6. When the integers become large, there is an efficient technique for finding their greatest common divisor, based on repeated use of Euclidean division. Clearly, gcd(a, b) = gcd(b, a) = gcd(±a, ± b), gcd(0, b) = |b| and gcd(b, b) = |b|. Thus, for the purpose of computing greatest common divisors of a and b, we need only consider the situation where 0 < a < b. If a, b are not both 0 and b = aq + r for some integers q, r, one can see that the set of common divisors of b and a is the same as the set of common divisors of a and r. Therefore gcd(b, a) = gcd(a, r). The preceding remark points the way for Euclidean division to find gcd(b, a). Say 0 < a < b. Apply Euclidean division repeatedly as follows: b = aq 1 + r 1 0 < r 1 < a a = r 1 q 2 + r 2 0 < r 2 < r 1 r 1 = r 2 q 3 + r 3 0 < r 3 < r 2 r 2 = r 3 q 4 + r 4 0 < r 4 < r 3 , to obtain strictly decreasing remainders r 1 > r 2 > r 3 > · · · ≥ 0. Sooner or later an integer remainder becomes 0. In other words, there must be an index n such that r n−3 = r n−2 q n−1 + r n−1 0 < r n−1 < r n−2 r n−2 = r n−1 q n + r n 0 < r n < r n−1 r n−1 = r n q n+1 + 0 0 = r n+1 . 4 A Refresher on the Integers From the remark preceding the above algorithm: r n = gcd(r n , 0) = gcd(r n−1 , r n ) = gcd(r n−2 , r n−1 ) = · · · = gcd(r 3 , r 4 ) = gcd(r 2 , r 3 ) = gcd(r 1 , r 2 ) = gcd(a, r 1 ) = gcd(b, a). The last positive remainder r n equals gcd(b, a). This famous process for obtaining greatest common divisors is called the Euclidean Algorithm. For example, here comes gcd(8316, 4641): 8316 = 4641 · 1 + 3675 4641 = 3675 · 1 + 966 3675 = 966 · 3 + 777 966 = 777 · 1 + 189 777 = 189 · 4 + 21 189 = 21 · 9 + 0.
eBook - PDF- Joachim von zur Gathen, Jürgen Gerhard(Authors)
- 2013(Publication Date)
- Cambridge University Press(Publisher)
Viewed either as a science of quantity, or as a language of symbols, it may be made of the greatest service to those who are sufficiently acquainted with arithmetic, and who have sufficient power of comprehension to enter fairly upon its difficulties. Augustus De Morgan (1837) 3 Ab¯ u Jafar Muh . ammad bin M¯ us¯ a al-Kh w¯ arizm¯ ı (c. 830) 1 Music has much resemblance to algebra. 2 A mathematician who is not somewhat of a poet will never be a perfect mathematician. 3 And this is an approximation and not a precise determination [of π]. Nobody can determine the exact value of that and know the circumference, except God. For this curve [the circle] is not straight and cannot be determined except approximately. That is called an approximation, just as the root of a number is an approximation and not the exact value; nobody knows it except God. 4 Applications of the Euclidean Algorithm This chapter presents several applications of the Extended Euclidean Algorithm: modular arithmetic, in particular modular inverses; linear Diophantine equations; and continued fractions. The latter in turn are useful for problems outside of com- puter algebra: devising astronomical calendars and musical scale systems. 4.1. Modular arithmetic We start with some applications. The first one is checking programs for correct- ness. In Part II of this book, we will see extremely fast algorithms for multiplica- tion of large integers. These methods are also considerably more complicated than classical multiplication, and an implementation quite error-prone.
No longer available |Learn more- (Author)
- 2014(Publication Date)
- Learning Press(Publisher)
• It is useful to define gcd(0, 0) = 0 and lcm(0, 0) = 0 because then the natural numbers become a complete distributive lattice with gcd as meet and lcm as join operation. This extension of the definition is also compatible with the generalization for commutative rings given below. ________________________ WORLD TECHNOLOGIES ________________________ • In a Cartesian coordinate system, gcd( a , b ) can be interpreted as the number of points with integral coordinates on the straight line joining the points (0, 0) and ( a , b ), excluding (0, 0). Probabilities and expected value In 1972, J. E. Nymann showed that the probability that k independently chosen integers are coprime is 1/ ζ ( k ). This result was extended in 1987 to show that the probability that k random integers has greatest common divisor d is d -k /ζ ( k ). Using this information, the expected value of the greatest common divisor function can be seen (informally) to not exist when k = 2. In this case the probability that the gcd equals d is d −2 /ζ(2), and since ζ(2) = π 2 /6 we have This last summation is the harmonic series, which diverges. However, when k ≥ 3, the expected value is well-defined, and by the above argument, it is For k = 3, this is approximately equal to 1.3684. For k = 4, it is approximately 1.1106. The gcd in commutative rings The greatest common divisor can more generally be defined for elements of an arbitrary commutative ring. If R is a commutative ring, and a and b are in R , then an element d of R is called a common divisor of a and b if it divides both a and b (that is, if there are elements x and y in R such that d · x = a and d · y = b ). If d is a common divisor of a and b , and every common divisor of a and b divides d , then d is called a greatest common divisor of a and b . Note that with this definition, two elements a and b may very well have several greatest common divisors, or none at all.
Index pages curate the most relevant extracts from our library of academic textbooks. They’ve been created using an in-house natural language model (NLM), each adding context and meaning to key research topics.
