AskSia
Plus
Prove that if gcd(a, b) = 1 and d | a + b, then gcd(a, d) = gcd(b, d) = 1.
Feb 20, 2024
Prove that if gcd(a, b) = 1 and d | a + b, then gcd(a, d) = gcd(b, d) = 1.
Solution by Steps
step 1
Given that gcd(a,b)=1 and d∣(a+b), we want to prove that gcd(a,d)=gcd(b,d)=1
step 2
Since d∣(a+b), there exists an integer k such that dk=a+b
step 3
Assume for contradiction that \gcd(a, d) > 1. Then there exists a prime p such that p∣a and p∣d
step 4
Since p∣a and p∣d, and dk=a+b, it follows that p∣b. This contradicts the assumption that gcd(a,b)=1
step 5
Therefore, our assumption is wrong, and we must have gcd(a,d)=1
step 6
Similarly, assume for contradiction that \gcd(b, d) > 1. Then there exists a prime q such that q∣b and q∣d
step 7
Since q∣b and q∣d, and dk=a+b, it follows that q∣a. This contradicts the assumption that gcd(a,b)=1
step 8
Therefore, our assumption is wrong, and we must have gcd(b,d)=1
Answer
gcd(a,d)=gcd(b,d)=1
Key Concept
Properties of gcd and divisibility
Explanation
If gcd(a,b)=1 and d divides a+b, then d cannot share any prime factors with a or b, otherwise it would contradict the fact that a and b are coprime. Hence, gcd(a,d)=gcd(b,d)=1.
© 2023 AskSia.AI all rights reserved