The Euclidean Algorithm

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.