Greatest Common Divisor

10 Key excerpts on "Greatest Common Divisor"

• 

  No longer available |Learn more

  Outline of Factorization in Mathematics

  • (Author)
  • 2014(Publication Date)
  • Learning Press

    (Publisher)

  ________________________ WORLD TECHNOLOGIES ________________________ Chapter 3 Greatest Common Divisor and Singular Value Decomposition Greatest Common Divisor In mathematics, the Greatest Common Divisor (gcd) , also known as the greatest common denominator , greatest common factor (gcf) , or highest common factor (hcf) , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 8 and 12 is 4. Overview The Greatest Common Divisor is useful for reducing fractions to be in lowest terms. For example, gcd(42, 56) = 14, therefore, The Greatest Common Divisor of a and b is written as gcd( a , b ), or sometimes simply as ( a , b ). For example, gcd(12, 18) = 6, gcd(−4, 14) = 2. Two numbers are called coprime or relatively prime if their Greatest Common Divisor equals 1. For example, 9 and 28 are relatively prime. Calculating the gcd Using prime factorizations Greatest Common Divisors can in principle be computed by determining the prime factorizations of the two numbers and comparing factors, as in the following example: to compute gcd(18, 84), we find the prime factorizations 18 = 2 · 3 2 and 84 = 2 2 · 3 · 7 and notice that the overlap of the two expressions is 2 · 3; so gcd(18, 84) = 6. In practice, this method is only feasible for small numbers; computing prime factorizations in general takes far too long. ________________________ WORLD TECHNOLOGIES ________________________ Here is another concrete example, illustrated by a Venn diagram. Suppose it is desired to find the Greatest Common Divisor of 48 and 180. First, find the prime factorizations of the two numbers: 48 = 2 × 2 × 2 × 2 × 3, 180 = 2 × 2 × 3 × 3 × 5. What they share in common is two 2s and a 3: Least common multiple = 2 × 2 × 2 × 2 × 3 × 3 × 5 = 720 Greatest Common Divisor = 2 × 2 × 3 = 12.

  Sign up to read

  Learn more about book
• 

  No longer available |Learn more

  Elementary Arithmetic & Important Concepts of Factorization

  • (Author)
  • 2014(Publication Date)
  • Library Press

    (Publisher)

  ________________________ WORLD TECHNOLOGIES ________________________ Chapter 8 Greatest Common Divisor and Singular Value Decomposition Greatest Common Divisor In mathematics, the Greatest Common Divisor (gcd) , also known as the greatest common denominator , greatest common factor (gcf) , or highest common factor (hcf) , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 8 and 12 is 4. Overview The Greatest Common Divisor is useful for reducing fractions to be in lowest terms. For example, gcd(42, 56) = 14, therefore, The Greatest Common Divisor of a and b is written as gcd( a , b ), or sometimes simply as ( a , b ). For example, gcd(12, 18) = 6, gcd(−4, 14) = 2. Two numbers are called coprime or relatively prime if their Greatest Common Divisor equals 1. For example, 9 and 28 are relatively prime. Calculating the gcd Using prime factorizations Greatest Common Divisors can in principle be computed by determining the prime factorizations of the two numbers and comparing factors, as in the following example: to compute gcd(18, 84), we find the prime factorizations 18 = 2 · 3 2 and 84 = 2 2 · 3 · 7 and notice that the overlap of the two expressions is 2 · 3; so gcd(18, 84) = 6. In practice, this method is only feasible for small numbers; computing prime factorizations in general takes far too long. ________________________ WORLD TECHNOLOGIES ________________________ Here is another concrete example, illustrated by a Venn diagram. Suppose it is desired to find the Greatest Common Divisor of 48 and 180. First, find the prime factorizations of the two numbers: 48 = 2 × 2 × 2 × 2 × 3, 180 = 2 × 2 × 3 × 3 × 5. What they share in common is two 2s and a 3: Least common multiple = 2 × 2 × 2 × 2 × 3 × 3 × 5 = 720 Greatest Common Divisor = 2 × 2 × 3 = 12.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Discrete Mathematics for Computing

  • Peter Grossman(Author)
  • 2017(Publication Date)
  • Red Globe Press

    (Publisher)

  This method is not computationally feasible in practice, however, because of the difficulty of factorising very large numbers. The methods currently used to find new primes involve a combination of advanced mathematical theory and substantial computations performed on a computer. 1 12.3 Greatest Common Divisors and the Euclidean algorithm In this section we will see how the Greatest Common Divisor of two non-negative integers can be found using one of the oldest algorithms still in use. Definitions Let a and b be non-negative integers, not both zero. The Greatest Common Divisor of a and b is the largest natural number m such that m | a and m | b . If a and b are both non-zero, the least common multiple of a and b is the smallest natural number m such that a | m and b | m . Two natural numbers a and b are coprime (or relatively prime ) if their Greatest Common Divisor is 1. The Greatest Common Divisor and least common multiple of a and b are denoted respectively by gcd( a , b ) and lcm( a , b ). For example: gcd(27, 45) = 9, gcd(15, 32) = 1, lcm(12, 18) = 36, lcm(11, 18) = 198. The numbers 15 and 32 are coprime. Both the Greatest Common Divisor (gcd) and the least common multiple (lcm) arise when we perform arithmetic with fractions. The gcd arises when a fraction is to be reduced to its lowest terms; for example, 27 45 can be simplified to 3 5 by dividing the numerator and the denominator by 9, the gcd of 27 and 45. The lcm arises as the ‘lowest common denominator’ when fractions are added; for example, when adding 5 12 and 7 18 , the fractions must first be expressed in terms of the common denominator 36, which is the lcm of 12 and 18.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  C++ for Mathematicians

  An Introduction for Students and Professionals

  • Edward Scheinerman(Author)
  • 2006(Publication Date)
  • CRC Press

    (Publisher)

  Chapter 3 Greatest Common Divisor 3.1 The problem For integers a and b , the Greatest Common Divisor of a and b is the largest integer d such that d is a factor of both a and b . The Greatest Common Divisor is denoted gcd ( a , b ) . We say a and b are relatively prime provided gcd ( a , b ) = 1. In this chapter we develop many C++ concepts by studying a particular problem involving the gcd of integers. Here is the classic problem: Let n be a positive integer. Two integers, a and b , are selected independently and uniformly from the set { 1 , 2 ,..., n } . Let p n be the probability that a and b are relatively prime. Does lim n → ∞ p n exist and, if so, what is its value? The computer cannot solve this problem for us, but it can help us to formulate a conjecture. We try a number of approaches including exhaustive enumeration, generating pairs of numbers at random and recording the results, and the use of Euler’s totient. The first order of business, however, is to develop a procedure to compute the Greatest Common Divisor of two integers. 3.2 A first approach In this section we develop a correct, but highly inefficient, procedure for calculat-ing the Greatest Common Divisor of two integers. Our goal is to introduce a number of C++ concepts as well as to create the gcd procedure. This procedure takes two integers and returns their Greatest Common Divisor. Later, we replace this inefficient procedure with a much more efficient method. Before we begin, however, we need to address a bit of terminology. Mathemati-cians and computer programmers use the word function differently. A mathemati-cian’s function assigns to each value x a unique value y = f ( x ) . Suppose we calculate, say f ( 8 ) and the result is 17. Then if we calculate f ( 8 ) a few minutes later, we are guaranteed that the result is still 17. 31

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Elementary Number Theory in Nine Chapters

  • James J. Tattersall(Author)
  • 2005(Publication Date)
  • Cambridge University Press

    (Publisher)

  Find a positive integer n such that n=2 is square, n=3 is cube, and n=5 is a fifth power. 2.2 The Greatest Common Divisor If a and b are integers and d is a positive integer such that d j a and d j b , then d is called a common divisor of a and b. If both a and b are zero then they have infinitely many common divisors. However, if one of them is nonzero, the number of common divisors of a and b is finite. Hence, there must be a largest common divisor. We denote the largest common divisor of a and b by gcd( a, b) and, following standard convention, call it 64 Divisibility the Greatest Common Divisor of a and b. It follows straightforwardly from the definition that d is the Greatest Common Divisor of a and b if and only if (1) d . 0, (2) dj a and d j b , (3) if ej a and ej b then ej d . As pointed out in [Schroeder], physiological studies have shown that, with few exceptions, the brain, upon being presented with two harmoni- cally related frequencies, will often perceive the Greatest Common Divisor of the two frequencies as the pitch. For example, if presented with frequencies of 320 hertz and 560 hertz the brain will perceive a pitch of 80 Hz. One of the most important properties of the Greatest Common Divisor of two numbers is that it is the smallest positive integer that can be expressed as a linear combination of the two numbers. We establish this result in the next theorem. Theorem 2.6 If a and b are not both zero and d ¼ gcd( a, b), then d is the least element in the set of all positive linear combinations of a and b. Proof Let T represent the set of all linear combinations of a and b that are positive, that is, T ¼ fax þ by: x and y are integers and ax þ by . 0g. Without loss of generality, suppose that a 6¼ 0. If a . 0, then a . 1 þ b . 0 ¼ a is in T . If a , 0, then a(1) þ b . 0 ¼ a is in T . Thus, in either case, T is a nonempty set of positive integers. By the well-ordering principle T contains a least element which we denote by e ¼ au þ bv .

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Abstract 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.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  An Experimental Introduction to Number Theory

  • Benjamin Hutz(Author)
  • 2018(Publication Date)
  • American Mathematical Society

    (Publisher)

  We also get another characterization of the Greatest Common Divisor. Corollary 1.25. If d | x and d | y , then d | gcd( x, y ) . Proof. From Theorem 1.22 we can write the gcd( x, y ) as a linear combination ax + by with a, b ∈ Z . If d | x and d | y , by Proposition 1.7 we have d | ax + by . Now we turn to the practical (computational) question of computing the gcd. Question 1.26. Given two integers x and y , how do we com-pute gcd( x, y ) and find the pair of integers ( a, b ) such that ax + by = gcd( x, y )? To compute the Greatest Common Divisor, we could simply test the divisibility of every positive integer at most min( | x | , | y | ) and find the largest that divides both x and y . While this takes a finite number of steps and is guaranteed to produce the Greatest Common Divisor, we hope for a more efficient solution. Additionally, this method gives us no information about ( a, b ). We describe the method of Euclid, 1 1 Euclid, also known as Euclid of Alexandria, was a Greek mathematician living around 300 B.C.E. 14 1. Integers called the Euclidean algorithm , that solves both of these problems at once in a very efficient manner. It relies on a connection between the Greatest Common Divisor of two numbers and the remainder from the division algorithm. Lemma 1.27. Let n and d be integers with d > 0 . Let q, r ∈ Z be the quotient and remainder from the division algorithm ( n = qd + r ) , then gcd( n, d ) = gcd( d, r ) . Proof. Let a = gcd( n, d ) and b = gcd( d, r ). We will show that a | b and that b | a , proving that a = b (Proposition 1.7). First we show a | b . From Theorem 1.22 we can find integers x and y such that (5) b = xd + yr. We also know that n = qd + r which is equivalent to r = n − qd. Substituting this expression for r into equation (5), we see that b = xd + y ( n − qd ) = ( x − qy ) d + yn. Since a | d and a | n , we have a | b by Proposition 1.7. Now we show b | a . We can find integers x and y such that a = xn + yd and n = qd + r.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Number Theory

  A Historical Approach

  • John J. Watkins(Author)
  • 2013(Publication Date)
  • Princeton University Press

    (Publisher)

  This algo-rithm produces in a step-by-step fashion the Greatest Common Divisor — that is, the highest common factor—of two numbers. Let’s see how the Euclidean algorithm works by looking at a simple example. Begin with two numbers 30 and 72. Divide the smaller number into the larger one and get a quotient 2 and a remainder 12, and write 72 = 2 · 30 + 12. Now, since 12 < 30 (that is why 12 was a remainder, after all), we can repeat this process and now divide 12 into 30 to get another quotient and remainder, and write 30 = 2 · 12 + 6. Repeat once 60 Chapter 3 more, dividing 6 into 12, and write 12 = 2 · 6 + 0. At this point the new remainder is 0 and the process stops, and we conclude that 6 is the Greatest Common Divisor of 30 and 72. Here are the three steps: 72 = 2 · 30 + 12 , 30 = 2 · 12 + 6 , 12 = 2 · 6 + 0 . How do we know that the algorithm has produced the Greatest Common Divisor? Well, we can tell that 6 is a common divisor of these two numbers 30 and 72, because the last equation shows us that 6 divides 12, and so, the previous equation then shows us that 6 divides 30 (since 6 divides both 6 and 12), and finally the first equation then shows us that 6 divides 72 (since we now know that 6 divides both 12 and 30). But we still need to conclude that 6 is the Greatest Common Divisor. Perhaps some larger number divides both 30 and 72. In order to do this, we will first work our way backwards through the steps above to express 6 as a linear combination of 30 and 72. So, begin with the next to last equation above, and write 6 = 30 − 2 · 12 . Then, working backwards, you can write the first equation as 12 = 72 − 2 · 30. This expression can now be substituted for 12 in the previous equation to get 6 = 30 − 2(72 − 2 · 30) = 5 · 30 − 2 · 72 . At this point, notice that 6 has been written entirely in terms of 30 and 72, that is, as a linear combination : 6 = 5 · 30 − 2 · 72 .

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Numbers, Groups and Codes

  • J. F. Humphreys, M. Y. Prest(Authors)
  • 2004(Publication Date)
  • Cambridge University Press

    (Publisher)

  Note It follows easily from the definition that if a divides b then the gcd of a and b is a . For instance gcd(6, 30) = 6. The proof of 1.1.2 actually showed the following very important property (you should go back and check this). Corollary 1.1.3 Let a and b be positive integers. Then the Greatest Common Divisor, d, of a and b is the smallest positive integral linear combination of a and b. ( By an integral linear combination of a and b we mean an integer of the form as + bt where s and t are integers. ) That is, d = as + bt for some integers s and t. For instance, the gcd of 12 and 30 is 6: we have 6 = 30 · 1 − 12 · 2. In Section 1.5 we give a method for calculating the gcd of any two positive integers. 8 Number theory We make some comment on what might be unfamiliar terminology. A ‘Corollary’ is supposed to be a statement that follows from another. So often, after a Theorem or a Proposition (a statement which, for whatever reason, is judged by the authors to be not quite as noteworthy as a Theorem) there might be one or more Corollaries. In the case above it was really a corollary of the proof, rather than the statement, of 1.1.2. The term ‘Lemma’, used below, indicates a result which we prove on the way to establishing something more notable (a Proposition or even a Theorem). Before stating the next main theorem we give a preliminary result. Lemma 1.1.4 Let a and b be natural numbers and suppose that a is non-zero. Suppose that b = aq + r with q and r positive integers. Then the gcd of b and a is equal to the gcd of a and r. Proof Let d be the gcd of a and b . Since d divides both a and b , d divides the (term on the) right-hand side of the equation r = b − aq : hence d divides the left-hand side, that is, d divides r . So d is a common divisor of a and r . Therefore, by definition of ( a , r ), d divides ( a , r ). Similarly, since the gcd ( a , r ) divides a and r and since b = aq + r , ( a , r ) must divide b .

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Mathematical Practices, Mathematics for Teachers

  Activities, Models, and Real-Life Examples

  • Ron Larson, Robyn Silbey(Authors)
  • 2014(Publication Date)
  • Cengage Learning EMEA

    (Publisher)

  The notation for the greatest common factor of a and b is written as GCF(a, b). To find the GCF(a, b), write the prime factorizations of a and b. The greatest common factor is the product of the common factors. Example a = 20, b = 12 a = 20 b = 12 2 2 5 3 Common factors a = 2 ⋅ 2 ⋅ 5 b = 2 ⋅ 2 ⋅ 3 GCF(20, 12) = 2 ⋅ 2 = 4 If a divides b, then GCF(a, b) = a. If b divides a, then GCF(a, b) = b. Example GCF(3, 12) = 3 EXAMPLE 1 Finding the Greatest Common Factor Find the greatest common factor of 16 and 24. SOLUTION Begin by writing the prime factorization of each number. a = 16: 16 b = 24: 24 4 4 4 6 2 2 2 2 2 2 2 3 So, 16 = 2 ⋅ 2 ⋅ 2 ⋅ 2 and 24 = 2 ⋅ 2 ⋅ 2 ⋅ 3. Next, use a diagram to organize the prime factors of a and b. a = 16 b = 24 2 2 2 2 3 Common factors The greatest common factor of 16 and 24 is 2 ⋅ 2 ⋅ 2 = 8. When you are teaching strategies for finding the GCF of two whole numbers, remind your students to first think about the numbers. 1. If both are primes, then the GCF is 1. GCF(3, 5) = 1 2. If one number is a multiple of the other, then the GCF is the lesser of the two numbers. GCF(3, 15) = 3 3. If one of the numbers is 0, then the GCF is the greater of the two numbers because 0 is divisible by any nonzero number. GCF(3, 0) = 3 Classroom Tip Standards Grades 3–5 Operations and Algebraic Thinking Students should gain familiarity with factors and multiples. Grades 6–8 The Number System Students should find common factors and multiples. Copyright 2014 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.

  Sign up to read

  Learn more about book