Prove that a given solution pair, x and y, must be relatively prime. [Hint: Supp

Question

Prove that a given solution pair, x and y, must be relatively prime.

[Hint: Suppose not and suppose that x = cr and y = cs. Use that to show that c divides d and write d = ct. Substitute all that back into ax + by = d and cancel out the c's. What does that tell you about t and d?]

Let a and b be in Z such that ax + by = d. Prove that a given solution pair, x and y, must be relatively prime. [Hint: Suppose not and suppose that x = cr and y = cs. Use that to show that c divides d and write d = ct. Substitute all that back into ax + by = d and cancel out the c's. What does that tell you about t and d?] epsilon Z and suppose that d = gcd(a, b). Then we know that there exist x, y

Explanation / Answer

If d = gcd(a,b), then d is the smallest positive integer that can be written as: ax + by = d for some x and y. Notice if gcd(a,b) = 1, this is the same statement as the one you wish to prove. Let's begin by assuming that g is the smallest positive number that can be written as ax + by for some x and y, or: ax + by = g Since d divides both a and b, d divides g as well, or: d

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.