#import "../../utils/core.typ": *

== Линейные диофантовы уравнения

#def[
    _Линейным диофантовым уравнением_ с двумя неизвестными называется уравнение вида $a x + b y = c$, где $a, b, c in ZZ$.
]

#def[
    _Решением линейного диофантова уравнения_ называется множество всех пар $(x, y) in ZZ^2: space a x + b y = c$.
]

#notice[
    Если $gcd(a, b) divides.not c$, то решение --- пустое множество, так как все линейные комбинации $a, b$ делятся на $gcd(a, b)$.
]

#notice[  
    Теперь заметим следующее: если $a x_1 + b y_1 = c$ и $a x_2 + b y_2 = c$, то $a(x_1 - x_2) + b(y_1 - y_2) = 0$.
    Иными словами, разность двух решений линейного диофантова уравнения --- решение соответствующего однородного уравнения.
]

А значит все решения линейного диофантова уравнения можно найти, решив однородное уравнение и прибавив ко всем его решениям какое-то решение исходного уравнения.

Решим однородное уравнение:

$a x + b y = 0 <==> a x = -b y$

Пусть $d = gcd(a, b), space a = d a', space b = d b'$

$a x = -b y <==> d a'x = -d b'y <==> a'x = -b'y limits(<==>)^star.op
cases(
    x = b'k,
    y = -a'k
), space k in ZZ$

$(star.op) space gcd(a', b') = 1 ==> a' divides y, space  b' divides x ==> x = b'k, space k in ZZ ==> y = -a'k$

Теперь найдём какое-то решение исходного уравнения, вспомнив о линейном представлении $gcd$:

$gcd(a, b) = d = a x_0 + b y_0 ==> c = d c' = a(c'x_0) + b(c'y_0)$

Таким образом, решение исходного уравнения: ${(c'x_0 + b'k, space  c'y_0 -a'k) divides k in ZZ}$, где:

$x_0, y_0$ --- коэффициенты при $a, b$ в линейном представлении $gcd(a, b)$,

$a' = (a)/(gcd(a, b)), space b' = (b)/(gcd(a, b)), space c' = (c)/(gcd(a, b))$

*Код на языке c++ который находит решение диофантового уравнения:*

```cpp
int extgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int x1, y1;
    int tmp = extgcd(b, a % b, x1, y1);
    x = y1, y = x1 - (a / b) * y1;
    return tmp;
}

void solve() {
    int a, b, c;
    cin >> a >> b >> c;
    int x, y;
    int gcd = extgcd(a, b, x, y);
    if (c % gcd != 0) {
        cout << "No solutions\n";
    } else {
        int k = c / gcd;
        cout << x * k << ' ' << b / gcd << '\n'; // c' * x_0 + b' * k
        cout << y * k << ' ' << -(a / gcd) << '\n'; // c' * y_0 - a' * k
    }
}
```

