Now we're getting somewhere. With the research questions in the preceding section complete, we now know all of the solutions to the equation
ax + by = d, where d = gcd(a, b). Therefore, it remains to determine all of the solutions to the equation
ax + by = c, where c = kd and k is 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 7x + 2y = 1. Let's change this a bit, say to
7x + 2y = 5. Using the Euclidean Algorithm, we found that x = 1, y = –3 is a solution to 7x + 2y = 1. Thus, it is easy to see that x = 1 · 5 = 5 and y = –3 · 5 = –15 is a solution to the equation 7 x + 2 y = 5. What about the other solutions? The applet from the previous section can be used to search for additional solutions:
Research Question 5
Suppose that gcd(a, b) = d and that (x0, y0) is a solution to ax + by = d. Find the general form of all solutions (x, y) to
ax + by = k d, giving x in terms of x0 and y in terms of y0.
Section 2.1 | Section 2.2 | Section 2.3 | Section 2.4 | Section 2.5
Copyright © 2001 by W. H. Freeman and Company