Suppose we wish to determine integers x,y such that 37x + 20y = 1209 Equations of this type are usually solved using what's called the Euclidean Algorithm, but a bare description of this algorithm in terms of modulo arithmetic is hard to follow for some students, mainly (I think) because they don't see the motivation behind each of the steps, so it just seems like a big recipe that happens to give the right answer. Let me see if I can describe the solution procedure in the most primitive terms, probably similar to the way in which Euclid's Algorithm was devised in the first place. Given the equation 37x + 20y = 1209, collect as many multiples of 20 as you can from each of the terms. This gives 20(x+y-60) + 17x = 9 Let's call the number in parentheses a, so we have a = x+y-60 and we can write the equation 20a + 17x = 9 Notice that this is an equation of the same form as the original, but with smaller coefficients. Let's repeat the procedure, this time collecting as many multiples of 17 as we can from each of the terms. The result is 17(a+x) + 3a = 9 Now let's call the number in parentheses b = a+x, so we have the equation 17b + 3a = 9 Repeating the procedure, this time we collect as many multiples of 3 as we can, giving 3(5b+a-3) + 2b = 0 Letting c denote the number in parentheses c = 5b+a-3 we have 3c + 2b = 0 Now repeat the procedure one more time, collecting multples of 2, to give 2(c+b) + c = 0 so if we set d = c+b we have the equation 2d + c = 0. At last we have an equation where one of the coefficients is 1, so we can say c = -2d. Now remember how we defined all of our parameters a,b,c,d d = c+b c = 5b+a-3 b = a+x a = x+y-60 We can substitute c=-2d into the first of these equations to give b = d - (-2d) = 3d. Then we can substitute c=-2d and b=3d into the second equation to give a = (-2d) - 5(3d) + 3 = -17d + 3 then we can substitute b=3d and a=-17d+3 into the 3rd equation to give x = (3d) - (-17d + 3) = 20d - 3 Now if we substitute x=20d-3 and a=-17d+3 into the 4th equation we find y = (-17+3) - (20d-3) + 60 = -37d + 66 Therefore, we have shown that the original equation is satisfied for integers x,y if and only if x = 20d - 3 y = -37d + 66 where d is any integer. We could tidy this up by setting k = d-1 to give the reduced form x = 20(k+1) - 3 = 20k + 17 y = -37(k+1) + 66 = -37k + 29 where k is any integer. Thus there are infinitely many solutions, the smallest of which is x=17, y=29. In general, if A,B,C have no common factors, the solution of Ax+By=C is of the form x = Bk + x0 y = -Ak + y0 where x0,y0 is a particular solution, whose values can be derived by the Euclidean Algorithm as illustrated above. Incidentally, if you're comfortable with modulo arithmetic, notice that the equation 37x + 20y = 1209 immediately implies x = 9/17 (mod 20) y = 5/4 (mod 37) so the solution is essentially equivalent to modulo division.

Return to MathPages Main Menu