## 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, , with two unknowns .

Theorem 1.4.4   The linear equation has no solutions if does not divide . If does divide then there are infinitely many solutions given by:

where , is any solution and is any integer.

proof: The first part of the theorem follows from lemma 1.2.4. Let , be any solution, and let be any other solution. We want to show that and , where . Substitute into the equation: :

Therefore, . If we can divide both sides of this equation by :

Since (see the Exercise 1.2.23), it follows that . Substituting into the above equation gives:

and our proof is complete.

Corollary 1.4.5   If then .

proof: Assume . Let . By the above theorem, there exist integers , such that . Since divides and divides , by the hypthothesis, it divides , by Lemma 1.2.4. Therefore .

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

Corollary 1.4.6   If and then .

David Joyner 2007-09-03