Линейное диофантово уравнение — это уравнение вида ax + by = c, где a, b и c — целые числа, а x и y нужно найти среди целых. ❓ Главный вопрос: существуют ли такие x и y, что равенство выполняется? Решение существует только если число c делится на наибольший общий делитель (НОД) чисел a и b. Если для уравнения ax + by = c, gcd(a, b) не делит c, то целых решений нет. gcd = НОД Если делит — решений бесконечно много, и их можно записать в общем виде. 📌 Пример: 3x + 7y = 1 НОД(3,7) = 1, а значит решение существует. Найдём одно частное решение Можно подобрать x = 5, y = -2, потому что 3*5 + 7*(-2) = 15 - 14 = 1...