Number Theory. If d=gcd(a,b,c) then d is a linear combination of a,b, and c

In summary, the conversation discusses the concept of greatest common divisors and linear combinations in mathematics. It is mentioned that if d is the greatest common divisor of three numbers a, b, and c, then it can be expressed as a linear combination of these numbers. However, the conversation focuses on proving this claim only for the greatest common divisor of two numbers, and the need for a proof for three numbers is mentioned. The use of the formula gcd(x, y) = px + qy is suggested to prove this claim.
  • #1
celtics777
22
0

Homework Statement


Several of us claimed that if d=gcd(a,b,c) then d is a linear combination of a,b and c, i.e. that d=sa+tb+uc for some integers s,t, and u. That is true, but we only proved the analogous claim for the greatest common divisor of two numbers, i.e. when d=gcd(a,b). We need three.



Homework Equations


N/A?



The Attempt at a Solution


I know that gcd(a,b,c)=gcd(gcd(a,b)c). Can I use this to prove? If so, I'm not sure how.
 
Physics news on Phys.org
  • #2
Sure. If you know that gcd(x, y)= px+ qy, then gcd(gcd(a,b), c)= p(gcd(a,b))+ qc.
And gcd(a, b)= sa+ tb so gcd(gcd(a,b), c)= p(sa+ tb)+ qc= (ps)a+ (pt)b+ qc and ps, pt, and q are integers.
 

FAQ: Number Theory. If d=gcd(a,b,c) then d is a linear combination of a,b, and c

1. What is number theory?

Number theory is a branch of mathematics that deals with the properties and relationships of integers. It focuses on studying patterns and structures within numbers and their interactions.

2. What is a linear combination?

A linear combination is a mathematical expression formed by multiplying each term with a constant and then adding them together. In the context of number theory, it refers to a combination of integers that can be expressed as a sum or difference of multiples of other integers.

3. How do you find the greatest common divisor (gcd) of three numbers?

The gcd of three numbers can be found by using the Euclidean Algorithm, which involves repeatedly dividing the larger number by the smaller number until the remainder is 0. The last non-zero remainder is the gcd.

4. Why is d=gcd(a,b,c) a linear combination of a,b, and c?

This is because the gcd is the largest integer that can divide all three numbers a, b, and c without any remainder. Therefore, it can be expressed as a combination of a, b, and c multiplied by some constants.

5. What is the significance of d=gcd(a,b,c) being a linear combination?

By expressing the gcd as a linear combination of a, b, and c, we can prove that the gcd of any set of numbers can always be expressed as a combination of those numbers. This is a fundamental property of gcd and is useful in solving many mathematical problems.

Similar threads

Can anyone please review/verify my proofs for gcd problem?
Replies
4
Views
1K
How to prove that d|c in gcd(ac,b) = gcd(c,b) if gcd(a,b) = 1?
Replies
1
Views
1K
How Do You Compute the GCD of Three Numbers Using Pairwise GCD?
Replies
1
Views
1K
Proving gcd(a+b,ab) = 1 for Relatively Prime Numbers
Replies
4
Views
1K
Number Theory. If d=gcd(a,b) then
Replies
1
Views
2K
U(n) as an External Direct Product
Replies
11
Views
1K
Tricky abstract algebra problem
Replies
20
Views
3K
Let d = gcd(a, b), prove kd = gcd(ka, kb)
Replies
1
Views
8K
Proving Greatest Common Divisor of a,b,c | Abstract Algebra 1
Replies
1
Views
2K
What is the implication of this algebraic problem?
Replies
1
Views
1K

Hot Threads

Recent Insights

Back
Top