.: Math
Math
> Number theory
> Integers
## IntegersProperties of the integers.## Sibling topics:## Contents:- Linear Diophantine non-solutions
- Linear Diophantine non-solutions 2
- Definition of a linear Diophantine equation
- Definition of relatively prime
Definition of a linear Diophantine equation
A linear Diophantine equation is an equation of the form `ax+by=c`, where all variables are integers.
Definition of relatively prime
Two numbers `x` and `y` are relatively prime means:
GCD(x,y)=1 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`.
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.
Proof: 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.)
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.
Proof: |