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

  • Thread starter Thread starter lordy12
  • Start date Start date
  • Tags Tags
    Gcd
Click For Summary
SUMMARY

The discussion focuses on proving the equality gcd(a,b,c) = gcd(a, gcd(b,c)) using linear combinations. Participants explore the relationship between the greatest common divisor (gcd) and prime factorization, emphasizing that gcd(a,b,c) can be expressed as a linear combination of its components. The conversation highlights the necessity of understanding linear combinations in the context of gcd calculations, particularly through the expression gcd(a,b,c) = ax + by + cz, where a, b, and c are integers and x, y, z are coefficients derived from their gcds.

PREREQUISITES
  • Understanding of linear combinations in number theory
  • Familiarity with the concept of greatest common divisor (gcd)
  • Knowledge of prime factorization techniques
  • Basic algebraic manipulation skills
NEXT STEPS
  • Study the properties of gcd and their proofs using linear combinations
  • Learn about the Euclidean algorithm for calculating gcd
  • Explore the relationship between gcd and least common multiple (lcm)
  • Investigate advanced number theory concepts such as Bézout's identity
USEFUL FOR

Mathematics students, educators, and anyone interested in number theory, particularly those studying gcd properties and linear combinations.

lordy12
Messages
36
Reaction score
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
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).
 

Similar threads

Proving that lcm(a,b)gcd(a,b)=ab
  • · Replies 8 ·
Replies
8
Views
5K
Finding GCD with Fibonacci: Base Case
  • · Replies 1 ·
Replies
1
Views
2K
How to prove that d|c in gcd(ac,b) = gcd(c,b) if gcd(a,b) = 1?
  • · Replies 1 ·
Replies
1
Views
2K
Order of a^m when gcd(m,n) = 1
  • · Replies 2 ·
Replies
2
Views
2K
[Abstract Algebra] GCD and Relatively Prime Proof
  • · Replies 5 ·
Replies
5
Views
2K
Can I Use Factor Sets to Solve GCD Problems?
  • · Replies 1 ·
Replies
1
Views
1K
Modular Congruence and GCD Proof
  • · Replies 1 ·
Replies
1
Views
1K
Undergrad Clarifications needed for an exercise in Hungerford's abstract algebra
  • · Replies 23 ·
Replies
23
Views
2K
Proving gcd(a+b,ab) = 1 for Relatively Prime Numbers
  • · Replies 4 ·
Replies
4
Views
2K
How Do You Compute the GCD of Three Numbers Using Pairwise GCD?
  • · Replies 1 ·
Replies
1
Views
2K