Эта статья входит в число добротных статей

Соотношение Безу

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Соотноше́ние Безу́ — представление наибольшего общего делителя целых чисел в виде их линейной комбинации с целыми коэффициентами[1].

Названо в честь французского математика Этьена Безу.

История[править | править вики-текст]

Впервые данный факт опубликовал в 1624 году французский математик Клод Гаспар Баше де Мезириак для случая взаимно простых чисел[2]. Этьен Безу в конце XVIII века обобщил теорему, распространив её на кольцо многочленов.

Формулировка[править | править вики-текст]

Пусть ,  — целые числа, хотя бы одно из которых не нуль. Тогда существуют такие целые числа , что выполняется соотношение:

НОД

которое называется соотношением Безу (для чисел и ), а также леммой Безу или тождеством Безу[3]. При этом целые числа называются коэффициентами Безу.

Примеры[править | править вики-текст]

  • НОД Соотношение Безу имеет вид:
    • Возможны и другие варианты разложения НОД, например:

Следствия[править | править вики-текст]

Если числа взаимно простые, то уравнение:

имеет целочисленные решения[4]. Этот важный факт облегчает решение диофантовых уравнений первого порядка.

НОД является наименьшим натуральным числом, которое может быть представлено в виде линейной комбинации чисел и с целыми коэффициентами[5].

Множество целочисленных линейных комбинаций совпадает с множеством кратных для НОД)[6].

Коэффициенты Безу[править | править вики-текст]

Поскольку случай, когда одно из чисел равно нулю, тривиален, далее в этом разделе предполагается, что оба эти числа не равны нулю.

Неоднозначность[править | править вики-текст]

Нахождение коэффициентов Безу эквивалентно решению диофантового уравнения первого порядка с двумя неизвестными:

где НОД

Или, что то же самое:

Отсюда следует, что коэффициенты Безу определены неоднозначно — если какие-то их значения известны, то всё множество коэффициентов даётся формулой[7]:

Ниже будет показано, что существуют коэффициенты Безу, удовлетворяющие неравенствам и

Вычисление коэффициентов с помощью алгоритма Евклида[править | править вики-текст]

Для нахождения коэффициентов Безу можно использовать расширенный алгоритм Евклида нахождения НОД и представить остатки в виде линейных комбинаций a и b[8]. Шаги алгоритма записываются в следующем виде:

Пример

Найдём соотношение Безу для Формулы алгоритма Евклида имеют вид:

Таким образом, НОД Из этих формул получаем:

В итоге соотношение Безу имеет вид:

Вычисление коэффициентов с помощью непрерывных дробей[править | править вики-текст]

Альтернативный (по существу эквивалентный) способ решения уравнения использует непрерывные дроби. Разделим обе части уравнения на НОД: Далее разложим в непрерывную дробь и подсчитаем подходящие дроби . Последняя (-я) из них будет равна и связана с предыдущей обычным соотношением:

Подставив в эту формулу и умножив обе части на получаем:

С точностью до знака, это соотношение Безу. поэтому предпоследняя подходящая дробь даёт модули решения: есть знаменатель этой дроби, а  — числитель. Осталось, исходя их первоначального уравнения, найти знаки для этого достаточно найти последние цифры в произведениях [9].

Минимальные пары коэффициентов[править | править вики-текст]

Приведенный в предыдущем разделе алгоритм через непрерывные дроби, как и эквивалентный ему алгоритм Евклида, даёт в результате пару удовлетворяющую неравенствам:

Этот факт следует из того, что дроби и , как указано выше, образуют последовательные подходящие дроби, а числитель и знаменатель следующей подходящей дроби всегда больше, чем у предыдущей[9] [10]. Для краткости можно назвать такую пару минимальной, таких пар всегда две.

Пример. Пусть НОД (12, 42) = 6. Ниже приведены некоторые элементы списка пар коэффициентов Безу, причём минимальные пары выделены красным цветом.

Применение[править | править вики-текст]

Соотношение Безу часто используется как лемма в ходе доказательства других теорем (например, основной теоремы арифметики[11]), а также для решения диофантовых уравнений и сравнений по модулю.

Решение диофантовых уравнений первой степени[править | править вики-текст]

Рассмотрим решение в целых числах диофантовых уравнений вида:

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

Тогда решением исходного уравнения будет пара[9] где

Решение сравнений первой степени[править | править вики-текст]

Для решения сравнений первой степени:

его достаточно преобразовать к виду[6]:

Практически важным частным случаем является нахождение обратного элемента в кольце вычетов, то есть решение сравнения:

Вариации и обобщения[править | править вики-текст]

Соотношение Безу легко обобщается на случай, когда имеется более двух чисел[1]:

Пусть , …,  — целые числа, не все равные нулю. Тогда существуют такие целые числа , …, , что выполняется соотношение:

НОД, …, =


Соотношение Безу может иметь место не только для целых чисел, но и в других коммутативных кольцах (например, для гауссовых целых чисел). Такие кольца называются кольцами Безу.

Пример: формулировка для кольца многочленов (от одной переменной):

Пусть  — какое-либо семейство многочленов, и не все они равны нулю. Обозначим их наибольший общий делитель. Тогда существует такое семейство многочленов , что выполняется соотношение:


Коэффициенты Безу для двух многочленов от одной переменной могут быть вычислены аналогично изложенному выше для целых чисел (с помощью расширенного алгоритма Евклида)[12]. Общие корни двух многочленов являются корнями также и их наибольшего общего делителя, поэтому из соотношения Безу и основной теоремы алгебры вытекает следующий результат:

Пусть даны многочлены и с коэффициентами в некотором поле. Тогда многочлены и такие, что , существуют тогда и только тогда, когда и не имеют общих корней ни в каком алгебраически замкнутом поле (обычно в качестве последнего берётся поле комплексных чисел).


Обобщением этого результата на любое количество многочленов и неизвестных является Теорема Гильберта о нулях.

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. 1 2 Хассе Г., 1953, с. 29..
  2. Claude Gaspard Bachet, sieur de Méziriac. Problèmes plaisants et délectables // Problemes plaisans, qui se font par nombres. — 2nd ed.. — Pierre Rigaud & Associates, 1624. — P. 18-33.
  3. Jones, G. A., Jones, J. M. §1.2. Bezout's Identity // Elementary Number Theory. — Berlin: Springer-Verlag, 1998. — P. 7—11.
  4. Хассе Г., 1953, с. 33..
  5. Фаддеев Д. К. Лекции по алгебре. Учебное пособие для вузов. — Наука, 1984. — С. 9. — 416 с.
  6. 1 2 Bezout's identity. Проверено 25 декабря 2014.
  7. Гельфонд А. О. Решение уравнений в целых числах. — Наука, 1983. — С. 9—10. — 63 с. — (Популярные лекции по математике, выпуск 8).
  8. Егоров Д. Ф. Элементы теории чисел. — Москва—Петроград: Госиздат, 1923. — С. 14. — 202 с.
  9. 1 2 3 Сушкевич А. К. Теория чисел. Элементарный курс. — Харьков: Изд-во Харьковского университета, 1954. — С. 49—51.
  10. Хинчин А. Я. Цепные дроби. — Изд. 3-е. — М.: ГИФМЛ, 1961. — С. 11—12.
  11. См., например: Жиков В.В. Основная теорема арифметики // Соросовский Образовательный Журнал. — 2000. — Т. 6, № 3. — С. 112–117.
  12. Коблиц Н. Курс теории чисел и криптографии. — М.: Научное изд-во ТВП, 2001. — С. 19. — 259 с. — ISBN 5-94057-103-4.

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]