Рівняння Безу

Означення

Рівняння Безу, або лема Безу, це теорема в елементарній теорії чисел, яка стверджує, що для будь-яких двох цілих чисел a та b існує унікальна пара цілих чисел s і t таких, що:

ax + by = НСД(a, b)

де НСД(a, b) — найбільший спільний дільник чисел a та b.

Знаходження s і t

Для знаходження s і t можна скористатися розширеним алгоритмом Евкліда або варіантом алгоритму, відомим як алгоритм зворотних підстановок:

1. Почніть з розширеного алгоритму Евкліда:

a = q1b + r1
b = q2r1 + r2
r1 = q3r2 + r3
…
rn-2 = qnrn-1 + rn

де qi — частки, а ri — залишки.

2. Зверніть послідовність залишків, щоб отримати таке:

rn
rn-1
…
r1

3. Для кожного залишку ri визначте відповідні коефіцієнти si і ti:

ri = si * a + ti * b

4. Зіставивши ці рівняння, отримаємо рівняння Безу:

ax + by = a * sn + b * tn = НСД(a, b)

де x = sn і y = tn.

Застосування

Рівняння Безу має численні застосування в теорії чисел, в тому числі:

• Знаходження оберненого елемента для елемента в кільці цілих чисел за модулем
• Розв'язування лінійних рівнянь в кільцях цілих чисел
• Знаходження НСД двох чисел
• Доведення інших теорем в теорії чисел

Випадки, коли s і t не цілі

У деяких випадках, якщо a і b не є цілими числами, розв'язки s і t рівняння Безу можуть бути не цілими. У таких випадках можна знайти цілі розв'язки, помноживши рівняння Безу на НСД(a, b).

Історія

Рівняння Безу назване на честь французького математика Етьєна Безу (1730-1783). Хоча воно відоме з давніх часів, перше його опубліковане доведення було представлено Ейлером у 1768 році.

Рівняння Безу є фундаментальним результатом в теорії чисел, який знаходить широкий спектр застосувань. Воно надає унікальний спосіб розв'язувати лінійні рівняння з цілочисельними коефіцієнтами та має важливе значення для розуміння структури кілець цілих чисел.

Запитання, що часто задаються

1. Для чого використовується рівняння Безу?
2. Як знайти s і t в рівнянні Безу?
3. Чи можуть s і t бути не цілими?
4. Хто вигадав рівняння Безу?
5. Як рівняння Безу пов'язане з алгоритмом Евкліда?

Залишити коментар

Опубліковано Максим на 13 05 2024. Поданий під Вікі. Ви можете слідкувати за будь-якими відповідями через RSS 2.0. Ви можете подивитись до кінця і залишити відповідь.