Соотноше́ние Безу́ — представление наибольшего общего делителя целых чисел в виде их линейной комбинации с целыми коэффициентами.
Названо в честь французского математика Этьена Безу.
История Впервые данный факт опубликовал в 1624 году французский математик Клод Гаспар Баше де Мезириак для случая взаимно простых чисел. Формулировка Баше следующая: «Даны два [взаимно] простых числа, найдите наименьшее кратное каждого из них, превышающее на единицу кратное другого». Для решения задачи Баше использовал алгоритм Евклида.
Этьен Безу в своём четырёхтомном «Курсе математики» (Cours de Mathematiques a l'usage des Gardes du Pavillon et de la Marine, том 3, 1766) обобщил теорему, распространив её на произвольные пары чисел, а также на многочлены.
Формулировка
Пусть , — целые числа, хотя бы одно из которых не ноль. Тогда существуют такие целые числа , что выполняется соотношение НОД
Это утверждение называется соотношением Безу (для чисел и ), а также леммой Безу или тождеством Безу. При этом целые числа называются коэффициентами Безу.
Существует также модификация соотношения Безу, ограниченная натуральными числами:
Пусть , — натуральные числа. Тогда существуют такие натуральные числа , что выполняется соотношение НОД
Примеры НОД Соотношение Безу имеет вид:
Возможны и другие варианты разложения НОД, например:
Следствия Если числа взаимно простые, то уравнение
имеет целочисленные решения. Этот важный факт облегчает решение диофантовых уравнений первого порядка.
НОД является наименьшим натуральным числом, которое может быть представлено в виде линейной комбинации чисел и с целыми коэффициентами.
Множество целочисленных линейных комбинаций совпадает с множеством кратных для НОД).
Коэффициенты Безу Поскольку случай, когда хотя бы одно из чисел равно нулю, тривиален, далее в этом разделе предполагается, что оба эти числа не равны нулю.
Неоднозначность Нахождение коэффициентов Безу эквивалентно решению диофантового уравнения первого порядка с двумя неизвестными: где НОД Или, что то же самое:
Отсюда следует, что коэффициенты Безу определены неоднозначно — если какие-то их значения известны, то всё множество коэффициентов даётся формулой
Ниже будет показано, что существуют коэффициенты Безу, удовлетворяющие неравенствам и .
Вычисление коэффициентов с помощью алгоритма Евклида
Для нахождения коэффициентов Безу можно использовать расширенный алгоритм Евклида нахождения НОД и представить остатки в виде линейных комбинаций a и b. Шаги алгоритма записываются в следующем виде:
…
Пример Найдём соотношение Безу для Формулы алгоритма Евклида имеют вид
Таким образом, НОД. Из этих формул получаем:
В итоге соотношение Безу имеет вид
Вычисление коэффициентов с помощью непрерывных дробей Альтернативный (по существу эквивалентный) способ решения уравнения использует непрерывные дроби. Разделим обе части уравнения на НОД: . Далее разложим в непрерывную дробь и подсчитаем подходящие дроби . Последняя из них будет равна и связана с предыдущей обычным соотношением:
Подставив в эту формулу и умножив обе части на , получаем
С точностью до знака, это соотношение Безу. поэтому предпоследняя подходящая дробь даёт модули решения: есть знаменатель этой дроби, а — числитель. Осталось, исходя из первоначального уравнения, найти знаки ; для этого достаточно найти последние цифры в произведениях .
Минимальные пары коэффициентов Приведённый в предыдущем разделе алгоритм через непрерывные дроби, как и эквивалентный ему алгоритм Евклида, даёт в результате пару , удовлетворяющую неравенствам
Этот факт следует из того, что дроби и , как указано выше, образуют последовательные подходящие дроби, а числитель и знаменатель следующей подходящей дроби всегда больше, чем у предыдущей. Для краткости можно назвать такую пару минимальной, таких пар всегда две.
Пример. Пусть . НОД(12, 42) = 6. Ниже приведены некоторые элементы списка пар коэффициентов Безу, причём минимальные пары выделены красным цветом:
Применение Соотношение Безу часто используется как лемма в ходе доказательства других теорем (например, основной теоремы арифметикиСм., например: ), а также для решения диофантовых уравнений и сравнений по модулю.
Решение диофантовых уравнений первой степени Рассмотрим решение в целых числах диофантовых уравнений вида
Обозначим НОД Очевидно, уравнение имеет целочисленные решения только в том случае, когда делится на . Будем считать это условие выполненным, и одним из приведённых выше алгоритмов найдём коэффициенты Безу :
Тогда решением исходного уравнения будет пара , где .
Решение сравнений первой степени Для решения сравнений первой степени
его достаточно преобразовать к виду
Практически важным частным случаем является нахождение обратного элемента в кольце вычетов, то есть решение сравнения
Вариации и обобщения Соотношение Безу легко обобщается на случай, когда имеется более двух чисел:
Пусть , …, — целые числа, не все равные нулю. Тогда существуют такие целые числа , …, , что выполняется соотношение: НОД, …, =
Соотношение Безу может иметь место не только для целых чисел, но и в других коммутативных кольцах (например, для гауссовых целых чисел). Такие кольца называются кольцами Безу.
Пример: формулировка для кольца многочленов (от одной переменной):
Пусть — какое-либо семейство многочленов, и не все они равны нулю. Обозначим их наибольший общий делитель. Тогда существует такое семейство многочленов , что выполняется соотношение:
Коэффициенты Безу для двух многочленов от одной переменной могут быть вычислены аналогично изложенному выше для целых чисел (с помощью расширенного алгоритма Евклида). Общие корни двух многочленов являются корнями также и их наибольшего общего делителя, поэтому из соотношения Безу и основной теоремы алгебры вытекает следующий результат:
Пусть даны многочлены и с коэффициентами в некотором поле. Тогда многочлены и такие, что , существуют тогда и только тогда, когда и не имеют общих корней ни в каком алгебраически замкнутом поле (обычно в качестве последнего берётся поле комплексных чисел).
Обобщением этого результата на любое количество многочленов и неизвестных является Теорема Гильберта о нулях.
См. также Алгоритм Евклида Диофантово уравнение Наибольший общий делитель Решение сравнений Сравнение по модулю
Примечания
Литература
Ссылки Онлайн-калькулятор коэффициентов соотношения Безу. Bezout’s Identity . Bezout’s identity, Euclidean algorithm.
Категория:Диофантовы уравнения Категория:Теоремы теории чисел Б