Note: If you cannot view some of the math on this page, you may need to add MathML support to your browser. If you have Mozilla/Firefox, go here and install the fonts. If you have Internet Explorer, go here and install the MathPlayer plugin.
Math > Number theory > Integers
IntegersProperties of the integers.
- Linear Diophantine non-solutions
- Linear Diophantine non-solutions 2
- Definition of a linear Diophantine equation
- Definition of relatively prime
Definition of a linear Diophantine equationA linear Diophantine equation is an equation of the form `ax+by=c`, where all variables are integers.
Definition of relatively primeTwo numbers `x` and `y` are relatively prime means:
Theorem: Linear Diophantine non-solutions
Given `a,b,c,d in ZZ`, if `d div a` and `d div b` and `d !div c`, then the equation `ax+by=c` has no integer solution for `x` and `y`.Proof: Assume by way of contradiction that the equation does have an integer solution. Then by Divisor divides multiples we know that `d div ax and d div by`, and by Divisor of a sum, we know that `d div (ax+by)`, which means that `d div c`. However, we've stated that `d !div c`, so that is impossible. Therefore, the equation has no solutions.
Corollary (of Linear Diophantine non-solutions): Linear Diophantine non-solutions 2
Given `a,b,c in ZZ` with `a` and `b` not both equal to zero, and `d=GCD(a,b)`. If the diophantine equation `ax+by=c` has an integer solution for `x` and `y`, then `d div c`. (Note that this is not the same as saying "If `d div c`, then the equation has a solution.)Proof: We'll prove this by proving the contrapositive: if `d !div c`, then the diophantine equation has no solutions. Because `d=GCD(a,b)`, `d div a and d div b` by the definition of GCD, and by applying Linear Diophantine non-solutions, we can see that the equation has no solutions.