꼴의 방정식을 디오판토스 방정식이라고 합니다.
이러한 방정식은 실수에서는 직선을 나타내지만, 자연수의 경우에는 이 방정식이 나타내는 집합이 그리 명확하지 않습니다.
예를 들어 $c \not\equiv 0 \pmod{gcd(a, b)}$이면 해는 확실히 존재하지 않습니다. 좌변은 최대공약수로 나누어떨어지지만 우변은 그렇지 않기 때문입니다.
나머지 경우에는 해가 존재한다는 것이 밝혀집니다. 방정식 $a’x + b’y = c’$로 넘어가면 충분합니다. 여기서 $a’ = \frac{a}{gcd(a, b)}$이고 $gcd(a’, b’) = 1$입니다. 그런 다음 방정식 $a’x + b’y = 1$을 풀기 위해 확장 유클리드 알고리즘을 사용하면 됩니다. 이렇게 얻은 해에 $c$를 곱해야 합니다.
모든 해를 얻으려면 $(x, y) \to (x + b’ \cdot k, y - a’ \cdot k), k \in \mathbb{Z}$로 변환하기만 하면 됩니다.