• Support PF! Buy your school textbooks, materials and every day products Here!

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

  • Thread starter celtics777
  • Start date
  • #1
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.
 

Answers and Replies

  • #2
HallsofIvy
Science Advisor
Homework Helper
41,833
955
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.
 

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

  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
2
Views
5K
Replies
6
Views
6K
  • Last Post
Replies
5
Views
2K
Replies
1
Views
2K
Replies
8
Views
3K
Replies
1
Views
1K
Top