ax + by-d where d= gcd( a, b). Therefore, it remains to determine all of the sol
ID: 3145842 • Letter: A
Question
ax + by-d where d= gcd( a, b). Therefore, it remains to determine all of the solutions to the equation ax+ by=kd, where kis an integer. To get a feel for what is going on, let's look at an example. In the preceding section, we looked at the equation 7 x +2y-1. Let's change this a bit, say to 7x + 2y-5 y 1. Thus, it is easy to see thatx-1à s 5 andy- -3a 5 is a solution to the equation 7x + 2y S. What about Using the Euclidean Algorithm, we found that x-1,y--3 is a solution to 7x+2 the other solutions? Let's put sols to work to find some others >sols (7,2,5,10) -9, 34) -7, 27) -5, 20) -3, 13) r-1, 6 1,-1 3,-B 5,-15) -22) 19, -29) Research Question 5 Suppose that gcd(a, b) = d and that (co-Y) is a solution to ax + by= d. Find the general form of all solutions (x,y) to ax +by-kd giving x in tems ofxo and y in tems ofyo-Explanation / Answer
Let x0, y0 be a solution.
The general form is x = x0 + (b/d)r and y = y0 - (a/d)r where r is any integer.
Proof:
We have
ax0 + by0 = kd
Let r be any integer.
Adding a(b/d)r and -a(b/d)r on LHS
=> ax0 + a(b/d)r +by0 - b(a/d)r = kd
=> a(x0 + (b/d)r) + b(y0 - (a/d)r) = kd
Thus x0 + (b/d)r and y0 - (a/d)r is the solution.
If (r,s) is a solution,
then ar + bs = kd,
ax0 + by0 = kd
Subtracting
=> a(r - x0) + b(s - y0) = 0
=> a(r - x0) = -b(s - y0)
=> Since a and b have gcd d, a/d and b/d have no common factors other than 1.
=> (r - x0) is a multiple of b/d and -(s - y0) is a multiple of a/d
=> r - x0 = mb/d and s - y0 = -la/d where m and l are integers
Thus r = x0 + mb/d, s = y0 - la/d and this is as per the earlier form.
Therefore every solution is of type x = x0 + rb/d and y = y0 - ra/d where k is any integer.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.