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:

$$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$ :

$$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$ :

$$\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:

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