Solve the linear diophantine equation 336m + 238n = 5558. Prove that there is a

Question

Solve the linear diophantine equation 336m + 238n = 5558. Prove that there is a unique pair of positive integers m and n satisfying this equation and find this solution.

Explanation / Answer

We use the Euclidean algorithm to find the GCD of 336 and 238. This applies the division algorithm iteratively as follows: 1. Divide 336 by 238 and write it in quotient/remainder form according to the division algorithm: 336 = 238q + r 336 = 238(1) + 98 2. Make 238 the new dividend and r = 98 the new divisor. Apply the division algorithm again: 238 = 98q + r 238 = 98(2) + 42 3. Make 98 the new dividend and r = 42 the new divisor. Apply the division algorithm again: 98 = 42q + r 98 = 42(2) + 14 4. Make 42 the new dividend and r = 14 the new divisor. Apply the division algorithm again: 42 = 14q + r 42 = 14(3) + 0. We have now reached a remainder of 0, so the Euclidean algorithm ends. The GCD of 336 and 238 was the last nonzero remainder, which was 14. Recall that we have a theorem that says the GCD is the least positive integer that can be written as 336x + 238y = 14, where x,y are integers. We can figure out what x and y are here by going backwards in the Euclidean algorithm. We found 14 via the step: 98 = 42(2) + 14, and we found 42 via the step 238 = 98(2) + 42, so we can plug in 238 - 98(2) for 42: 98 = (238 - 98(2))(2) + 14 98 - 238(2) + 98(4) = 14 98(5) - 238(2) = 14. Working backward further in our Euclidean algorithm steps, we found 98 via 336 = 238(1) + 98, or 98 = 336 - 238(1), which we can plug in: (336 - 238(1))(5) - 238(2) = 14 336(5) - 238(5) - 238(2) = 14 336(5) - 238(7) = 14 or 336(5) + 238(-7) = 14. We find a solution to 336m + 238n = 5558 by noting that 5558/14 = 397, and multiplying both sides through by 397: 336(1985) + 238(-2779) = 5558. So m = 1985, n = -2779 is one solution for this linear diophantine equation. If such an equation has one solution, however, it has infinite solutions, and we want a positive one. First we find the general solution. Recall that the general solution x,y to an equation of the form ax + by = c with particular solution X,Y is x = X + (bk)/d, y = Y - (ak)/d, where k is any integer and d is the GCD. Why? Plug these in: a(X + bk/d) + b(Y - ak/d) = aX + abk/d + bY - abk/d = aX + bY = c, since X,Y was a particular solution. This shows X + bk/d, Y - ak/d is also a solution. So for our equation 336m + 238n = 5558, we have particular solution m = 1985, n = -2779, and the general solution is m = 1985 + (238k)/14 = 1985 + 17k, n = -2779 - (336k)/14 = -2779 - 24k. This is the general solution. Now we want to choose k so as to make n positive: -2779 - 24k > 0 24k < -2779 k < -115.8 (approx.) but we also want k to be such that m is still positive: 1985 + 17k > 0 17k > -1985 k > -116.8 (approx.). So k must be an integer between -115.8 and -116.8. There is only one possibility: k = -116. So the solution m = 1985 + 17k = 1985 + 17(-116) = 13, n = -2779 - 24k = - 2779 - 24(-116) = 5 is the only solution with both positive m and n -- the unique positive solution we are looking for. We check that this works: 336(13) + 238(5) = 5558, as desired, so m = 13, n = 5 is confirmed as our solution.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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