Linear Diophantine Equations
The equation has a solution in integers exactly when divides .
Corollary 4.13 (Bézout's Identity, Continued)
Let . Then the equation has a solution with if and only if .
Proof
Suppose first that for some , and let . Since divides and divides , we have .
Conversely, suppose that . By Bézout’s identity there exist with , and then
giving a solution.
Example
Does have integer solutions? Since divides , the criterion applies: by Bézout’s identity we can write for some , and therefore
Integer solutions do exist.
Related
Stated in
- Corollary 4.13 (Bézout's Identity, Continued)§4.3 Euclid’s Algorithm