## 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$.

• 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)?

• nbloomf  On December 3, 2011 at 12:36 am

Thanks!

• 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.