Метод Безу используется для нахождения целых решений линейного диофантова уравнения, а также для нахождения наибольшего общего делителя (НОД) двух чисел. Давайте рассмотрим, как это сделать на конкретном примере.

Предположим, у нас есть уравнение:

ax + by = d,

где a и b - целые числа, d - общий делитель a и b.

Шаги решения:

1. Находим НОД: Сначала нужно найти НОД чисел a и b с помощью алгоритма Евклида. Это даст нам значение d.
2. Записываем НОД в виде линейной комбинации: После нахождения НОД, мы должны выразить его через a и b. Для этого используем обратный ход алгоритма Евклида.
3. Находим общее решение: Если мы выразили d как ax + by = d, то общее решение можно записать в виде:
   • x = x0 + (b/d)t,
   • y = y0 - (a/d)t,
   где (x0, y0) - одно из частных решений, а t - любое целое число.
4. Подставляем значения: Подставляем найденные значения x0 и y0 в общее решение и находим все целые решения уравнения.

Теперь давайте рассмотрим конкретный пример:

Решим уравнение 30x + 21y = 3.

1. Находим НОД:
   • 30 = 21 * 1 + 9
   • 21 = 9 * 2 + 3
   • 9 = 3 * 3 + 0
   НОД(30, 21) = 3.
2. Записываем НОД в виде линейной комбинации:
   • 3 = 21 - 9 * 2
   • 9 = 30 - 21 * 1
   • Подставляем: 3 = 21 - 2 * (30 - 21) = 3 * 21 - 2 * 30.
   Таким образом, x0 = -2, y0 = 3.
3. Общее решение:
   • x = -2 + 7t,
   • y = 3 - 10t,
   где t - любое целое число.

Таким образом, мы нашли общее решение данного уравнения. Вы можете подставлять разные значения t, чтобы получить различные целые решения.