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

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

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

ИсторияПравить

Впервые данный факт опубликовал в 1624 году французский математик Клод Гаспар Баше де Мезириак для случая взаимно простых чисел[2]. Формулировка Баше следующая: «Даны два [взаимно] простых числа, найдите наименьшее кратное каждого из них, превышающее на единицу кратное другого»[3]. Для решения задачи Баше использовал алгоритм Евклида.

Этьен Безу в своём четырёхтомном «Курсе математики» (Cours de Mathematiques a l'usage des Gardes du Pavillon et de la Marine, том 3, 1766) обобщил теорему, распространив её на произвольные пары чисел, а также на многочлены[⇨].

ФормулировкаПравить

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

НОД 

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

Существует также модификация соотношения Безу, ограниченная натуральными числами[5]:

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

НОД 

ПримерыПравить

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

СледствияПравить

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

 

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

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

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

Коэффициенты БезуПравить

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

НеоднозначностьПравить

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

  где   НОД 

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

 

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

 

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

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

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

 
 
 
 
Пример

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

 
 
 

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

 
 

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

 

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

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

 

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

 

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

Минимальные пары коэффициентовПравить

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

 

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

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

 

ПрименениеПравить

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

Решение диофантовых уравнений первой степениПравить

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

 

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

 

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

Решение сравнений первой степениПравить

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

 

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

 

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

 

Вариации и обобщенияПравить

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

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

НОД , …,   =  

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

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

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

 

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

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

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

См. такжеПравить

ПримечанияПравить

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

ЛитератураПравить

СсылкиПравить