## Math

**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

### Integers

Properties 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:*