Prove that for every integer t, if there exist integers m andn such that 15m + 1

Question

Prove that for every integer t, if there exist integers m andn such that 15m + 16n = t, then there exist integers r and s suchthat 3r + 8s = t. I would assume you approach this by contradiction, but I'm notsure what to do past that... I would appreciate any help onthis! Prove that for every integer t, if there exist integers m andn such that 15m + 16n = t, then there exist integers r and s suchthat 3r + 8s = t. I would assume you approach this by contradiction, but I'm notsure what to do past that... I would appreciate any help onthis!

Explanation / Answer

We're given that 15m + 16n = t => gcd(15,16) = t => t | 15, t | 16 , where we could also write 15 and16 in their factorized form (where they are written as a product ofprimes) t | 15 = (1)(3)(5), t | 16 =(1)(2)(2)(2)(2) => t divides the greatest common element. In this case, theonly common element is 1. => t = 1, and so 15 and 16 are relatively prime (which isobvious by looking, but just pretend otherwise...)
So now, we can choose some divisors of 15 and 16 (that arealso able to be divided by t) We can choose 3 from 15 = (3)(5) and 8 from 16 = (2)(2)(2)(2)= (8)(2) And of course, t | 3 and t | 8 => gcd (3,8) = t => 3r + 8s = t
And that completes the proof.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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