GCD Associativity: Proving gcd(a,b,c) with Linear Combinations

  • Thread starter lordy12
  • Start date
  • Tags
    Gcd
In summary, GCD associativity is a property of the greatest common divisor (GCD) of three or more numbers, where the GCD can be computed by finding the GCD of any two numbers, followed by the GCD of the result and the third number. It is proven using linear combinations and is important because it simplifies the calculation of GCD for multiple numbers. The GCD associativity can be extended to any number of numbers, but it only applies to positive integers and is not applicable when finding the GCD of only two numbers.
  • #1
lordy12
36
0
1.Show gcd(a,b,c) = gcd(a, gcd(b,c))



Homework Equations





3. My attempt is that gcd(a,b,c) can be written as the product of their prime factors. Let's say x is that product. The thing is, I know how to prove this using prime factorization but there has to be another method concerning linear combinations. Like gcd(a,b,c) = ax + by+ cz.
 
Physics news on Phys.org
  • #2
Why not just say a= nx, b= ny, c= nz where n= gcd(a,b,c).
Of course, you also have b= mp, c= mq where m= gcd(b,c).
 

1. What is the definition of GCD associativity?

GCD associativity is a property of the greatest common divisor (GCD) of three or more numbers. It states that the GCD of three numbers, a, b, and c, can be computed as the GCD of any two of the numbers, followed by the GCD of the result and the third number. In other words, it does not matter which two numbers are initially chosen to compute the GCD, as long as all three numbers are included in the final calculation.

2. How is the GCD associativity proven?

The GCD associativity can be proven using linear combinations. This involves expressing the GCD of three numbers, a, b, and c, as a linear combination of the three numbers, where the coefficients are integers. By finding the GCD of two of the numbers and the remaining number, and then substituting the linear combination of the three numbers into the GCD formula, it can be shown that the result is the same regardless of which two numbers are initially chosen.

3. Why is GCD associativity important?

GCD associativity is important because it simplifies the calculation of GCD for three or more numbers. Instead of having to compute the GCD of all the numbers at once, it can be broken down into smaller steps. This makes it easier to perform by hand and also allows for the use of algorithms that are more efficient when calculating the GCD of two numbers.

4. Can GCD associativity be extended to more than three numbers?

Yes, GCD associativity can be extended to any number of numbers. This means that the GCD of four or more numbers can be computed by repeatedly finding the GCD of two numbers and the remaining numbers. As long as all the numbers are included in the final calculation, the result will be the same regardless of the order in which the GCDs are performed.

5. Are there any limitations to GCD associativity?

One limitation of GCD associativity is that it only applies to positive integers. It cannot be used to compute the GCD of negative numbers or numbers with decimals. Additionally, GCD associativity only applies to finding the GCD of three or more numbers. It is not applicable when finding the GCD of only two numbers.

Similar threads

  • Calculus and Beyond Homework Help
Replies
8
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
863
  • Calculus and Beyond Homework Help
Replies
1
Views
949
  • Calculus and Beyond Homework Help
Replies
1
Views
851
  • Calculus and Beyond Homework Help
Replies
4
Views
983
  • Calculus and Beyond Homework Help
Replies
11
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
2K
Back
Top