Linear Diophantine Equations

    The term Diophantine equation usually refers to any equation in one or more unknowns that is to b solved in the integers. The simplest kind of Diophantine equation is the linear Diophantine equation, namely a x + b y = c. In general, Diophantine equations furnish a natural vehicle for puzzles and problems of a mathematical nature.

Proposition (Linear Diophantine Equation) The linear Diophantine equation has a solution if and only if where Moreover, if is a solution, then the set of solutions of the equation consists of integers pairs where and for any integer
    
    Proof. Since there exists integers and such that Since we have an integer such that and thus we have Whence, and so we have a solution. Conversely, suppose has a solution say and Then and since and we have
    Let and be any solution. Then we have and so



for any integer Therefore, are solutions for any integer
    It remains to show that all solutions have the form and for any integer and any particular solution Let be any solutions and let be any particular solution so then we have and thus Now enter . Dividing by we have



Observe that and so Therefore, there exists an integer such that and whence, and by substitution, as desired.

Example (Linear Diophantine Equation) Solve the linear Diophantine equation

    Solution. Since and There is a solution and they are all given by and for any integer and so we need to find an initial solution. Since an initial solution is and we have all solutions and

Example (Linear Diophantine Equation) Solve the linear Diophantine equation

    Solution. Since and There is a solution and they are all given by and for any integer and so we need to find an initial solution. Since an initial solution is and we have all solutions and

Example (Linear Diophantine Equation) Solve the linear Diophantine equation

    Solution. Since and There is no solution.

Proposition (Linear Diophantine Equation) If and if and is a particular solution of the linear Diophantine equation then all solutions are given by and for integral values of

Example (Linear Diophantine Equation) The equation has as one solution and so a complete solution is given by and for arbitrary integral values of

Proposition (Linear Diophantine Equation) If are nonzero positive integers, then the equation has an integral solution if and only if divides Furthermore, when there is a solution, there are infinitely many solutions.

Example (Linear Diophantine Equation) Which combinations of pennies, dimes, and quarters have a total value of

    Solution. Let and be the number of pennies, dimes, and quarters, respectively. To solve this question we must solve the linear Diophantine equation:
    


Since and are all positive integers, it follows that and so we can solve the 4 corresponding equations in only and
    First, we solve Clearly, and is a particular solution and since all solutions are given by and By letting range from 0 to , we find



    Next, we solve Clearly, and is a particular solution and since all solutions are given by and By letting range from 0 to , we find



    Next, we solve Clearly, and is a particular solution and since all solutions are given by and By letting range from 0 to , we find



    Finally, we solve Clearly, and is a particular solution and since all solutions are given by and By letting range from 0 to , we find

• print this page
• pages linking here
• related pages