Number Theory. If d=gcd(a,b) then

Click For Summary
To show that gcd(a/d, b/d) = 1 when d = gcd(a, b), it is necessary to demonstrate that 1 can be expressed as a linear combination of a/d and b/d. The approach involves dividing both a and b by their greatest common divisor, d, which simplifies the problem. The key insight is that since d is the gcd of a and b, a and b can be expressed as linear combinations of their respective multiples. Thus, the relationship implies that a/d and b/d are coprime, confirming that gcd(a/d, b/d) equals 1. This conclusion is essential for understanding the properties of gcd in number theory.
celtics777
Messages
22
Reaction score
0

Homework Statement


If d=gcd(a,b) show that gcd((a/d),(b/d))=1



Homework Equations


N/A?



The Attempt at a Solution


Basically, I know that I need to show that 1 is a linear combination of a/d and b/d. I'm not exactly sure how to go about this. Dividing by d gives (d/d)=1=gcd(a/d,b/d) if that's correct, does that get me anywhere?
 
Physics news on Phys.org
If d = gcd(a,b), then what does that imply about linear combinations of a and b?
 

Thread 'Distance between a Clock's hands when the distance is increasing most rapidly'

Question: A clock's minute hand has length 4 and its hour hand has length 3. What is the distance between the tips at the moment when it is increasing most rapidly?(Putnam Exam Question) Answer: Making assumption that both the hands moves at constant angular velocities, the answer is ## \sqrt{7} .## But don't you think this assumption is somewhat doubtful and wrong?
View full post »

Similar threads

Can I Use Factor Sets to Solve GCD Problems?
  • · Replies 1 ·
Replies
1
Views
1K
How to prove that d|c in gcd(ac,b) = gcd(c,b) if gcd(a,b) = 1?
  • · Replies 1 ·
Replies
1
Views
1K
Number theory GCD relatively prime question
  • · Replies 5 ·
Replies
5
Views
2K
Proving gcd(a+b,ab) = 1 for Relatively Prime Numbers
  • · Replies 4 ·
Replies
4
Views
1K
Modular Congruence and GCD Proof
  • · Replies 1 ·
Replies
1
Views
1K
Proving that lcm(a,b)gcd(a,b)=ab
  • · Replies 8 ·
Replies
8
Views
4K
How to Find 13 Solutions of ax ≡ 26 (mod 78)
  • · Replies 18 ·
Replies
18
Views
2K
Number theory, primitive pythagorean triples
  • · Replies 6 ·
Replies
6
Views
2K
How Do You Compute the GCD of Three Numbers Using Pairwise GCD?
  • · Replies 1 ·
Replies
1
Views
2K
Number Theory. If d=gcd(a,b,c) then d is a linear combination of a,b, and c
  • · Replies 1 ·
Replies
1
Views
3K