Застосування
Одне поширене застосування рівняння Безу — пошук оберненого модуля. Якщо gcd(a, b) = 1, обернений a степенем b по модулю b можна знайти за допомогою розширеного алгоритму Евкліда, який дає нам a * x + b * y = gcd(a, b), де x — це обернений a степенем b по модулю b.
Іншим застосуванням рівняння Безу є знаходження найменшого спільного кратного (НСК) двох чисел. НСК (a, b) можна обчислити як a * b / gcd(a, b), використовуючи рівняння Безу для знаходження GCD.
Доведення
Доведення рівняння Безу може бути проведено за допомогою індукції.
Базовий випадок: Для a = 0, рівняння Безу стає 0 * x + b * y = gcd(0, b) = b, що є явно істинним.
Індуктивний крок: Припустимо, що рівняння Безу виконується для пари чисел (a, b). Ми повинні показати, що воно також виконується для пари (b, r), де r — залишок від ділення a на b.
Оскільки a = b * q + r, де q — ціле число, ми можемо підставити це в рівняння Безу для пари (a, b):
a * x + b * y = gcd(a, b)
(b * q + r) * x + b * y = gcd(a, b)
b * (q * x + y) + r * x = gcd(a, b)
Оскільки b є дільником gcd(a, b), ми можемо винести його за дужки:
b * (q * x + y + x * (r / gcd(a, b))) = gcd(a, b)
Оскільки b * (q * x + y + x * (r / gcd(a, b))) — це ціле число, а gcd(a, b) — найбільший спільний дільник a і b, це означає, що gcd(b, r) повинен також ділити gcd(a, b). Оскільки r < b, це означає, що gcd(b, r) = gcd(a, b).
Таким чином, ми показали, що рівняння Безу виконується для пари (b, r).
Рівняння Безу є потужним інструментом в елементарній теорії чисел, який має численні застосування, включаючи пошук обернених модулів і обчислення найменшого спільного кратного.
Часті запитання
- Що таке рівняння Безу?
- Як використовувати рівняння Безу для знаходження обернених модулів?
- Як використовувати рівняння Безу для знаходження НСК?
- Як довести рівняння Безу?
- Які ще застосування рівняння Безу?