Solve linear Diophantine equations in two variables in a Euclidean domain

Let R be a Euclidean Domain.

  1. Prove that if \mathsf{gcd}(a,b) = 1 and a divides bc, then a divides c. More generally, show that if a divides bc with a,b \neq 0, then a/(\mathsf{gcd}(a,b) divides c.
  2. Consider the Diophantine Equation ax + by = N, where a, b, and N are integers and a,b \neq 0. Suppose x_0,y_0 is a solution- that is, ax_0 + by_0 = N. Prove that the full set of solutions to this equation is given by x = x_0 + mb/\mathsf{gcd}(a,b) and y = y_0 - ma/\mathsf{gcd}(a,b) as m ranges over the integers.

  1. Suppose first that \mathsf{gcd}(a,b) = 1 and that a|bc. By Theorem 4, there exist x,y \in R such that ax + by = 1. Then axc = byc = c. Since a|bc, we have bc = ak for some k \in R. So axc + ayk = c, and thus a(xc + yk) = c. So a|c.

    More generally, say \mathsf{gcd}(a,b) = d, a = da^\prime, and b = db^\prime. Again by Theorem 4, we have x,y \in R such that ax + by = d. Since a|bc, we have bc = ak = da^\prime k for some k \in R. Now axc + byc = dc, so that da^\prime xc + da^\prime ky = dc, and thus da^\prime(cx + ky) = dc Since R is an integral domain, a^\prime(cx + ky) = c, and thus a^\prime = a/d divides c.

  2. Write \mathsf{gcd}(a,b) = d, and suppose (x,y) is a solution to ax + by = N. Then (ax + by) - (ax_0 + by_0) = N-N = 0, so that a(x-x_0) = b(y_0-y). Since b divides a(x-x_0), we have that b/d divides x-x_0. Say bm/d = x-x_0; then x = x_0 + mb/\mathsf{gcd}(a,b). Substituting into ax + by = N, we see that a(x_0 + mb/\mathsf{gcd}(a,b)) + by = N = ax_0 + by_0, so that mab/\mathsf{gcd}(a,b) + by = by_0. Since \mathsf{gcd}(a,b) divides a and R is a domain, we have y = y_0 - ma/\mathsf{gcd}(a,b).

    Moreover, it is straightforward to show (as we did in this previous exercise) that every pair of this form is in fact a solution. Thus we have completely characterized the solutions of ax + by = N.

Post a comment or leave a trackback: Trackback URL.


  • Will  On November 30, 2011 at 10:12 pm

    In part 2, isn’t it that a(x – x_0) = b(y_0 – y), rather than a(x – x_0) = b(y – y_0)?

  • amos dusabe  On December 16, 2011 at 8:08 am

    please send for me revision questios..

  • amos dusabe  On December 16, 2011 at 8:11 am

    send for me solved examples

    • nbloomf  On December 16, 2011 at 11:33 am

      It’s not too hard to make up examples- just pick any numbers for a, b, x_0, and y_0.

      For instance, with a = 15 and b = 13, the equation 15x + 13y = 7 has (-3,4) as a solution. Every other solution has the form (-3+13m, 4-15m) where m is an arbitrary integer.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: