Linear diophantine equations

Diophantus, a Greek mathematician who lived during the 4th century A.D., was one of the first people who attempted to find integral or rational solutions to a given system of equations. Often the system involves more unknowns than equations. We will consider a linear equation, $ ax+by=c$, with two unknowns $ x,y$.

Theorem 1.4.4   The linear equation $ ax+by=c$ has no solutions if $ gcd(a,b)$ does not divide $ c$. If $ gcd(a,b)$ does divide $ c$ then there are infinitely many solutions given by:

$\displaystyle x=x_0+ \frac{b}{gcd(a,b)}\,t, \quad y=y_0-\frac{a}{gcd(a,b)}\,t , $

where $ x=x_0$, $ y=y_0$ is any solution and $ t$ is any integer.

proof: The first part of the theorem follows from lemma 1.2.4. Let $ x=x_0$, $ y=y_0$ be any solution, and let $ x=r,\,y=s$ be any other solution. We want to show that $ r=x_0+\frac{b}{d}t$ and $ s=y_0-\frac{a}{d}\,t$, where $ d=gcd(a,b)$. Substitute into the equation: $ ax+by=c$:

$\displaystyle 0=c-c=ar+bs-(ax_0+by_0)=a(r-x_0)+b(s-y_0). $

Therefore, $ a(r-x_0)=b(y_0-s)$. If $ d > 1$ we can divide both sides of this equation by $ d$:

$\displaystyle \frac{a}{d}(r-x_0)=\frac{b}{d}(y_0-s). $

Since $ (\frac{a}{d},\frac{b}{d})=1$ (see the Exercise 1.2.23), it follows that $ \frac{a}{d} \,\mid (y_0-s)$. Substituting $ y_0-s=\frac{a}{d}\,t$ into the above equation gives:

$\displaystyle r-x_0=\frac{d}{a}\,\frac{b}{d}\,(y_0-s) =\frac{b}{a}\,t\,\frac{a}{d}=\frac{b}{d} t , $

and our proof is complete. $ \Box$

Corollary 1.4.5   If $ a \,\mid \,bc$ then $ a \,\mid \,gcd(a,b)\cdot c$.

proof: Assume $ a\,\mid bc$. Let $ d=gcd(a,b)$. By the above theorem, there exist integers $ x$, $ y$ such that $ ax+by=d$$ , so acx+bcy=dc$. Since $ a$ divides $ acx$ and $ a$ divides $ bcy$, by the hypthothesis, it divides $ acx+bcy$, by Lemma 1.2.4. Therefore $ a \,\mid \,(a,b)c$. $ \Box$

The following corollary is an immediadiate consequence of the previous one.

Corollary 1.4.6   If $ a \,\mid \,bc$ and $ gcd(a,b)=1$ then $ a\mid c$.


David Joyner 2007-09-03