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

В теории чисел соотноше́ние Безу́ — соотношение между парой целых чисел и их наибольшим общим делителем, названное в честь французского математика Этьена Безу:

Пусть a, b — целые числа, хотя бы одно из которых не нуль. Тогда существуют такие целые числа x, y, что выполняется соотношение: НОД(a,b) = x·a + y·b.

Другими словами, наибольший общий делитель чисел a, b можно всегда представить как линейную комбинацию a и b с целыми коэффициентами.

Соотношение НОД(a,b) = x·a + y·b называется соотношением Безу (для чисел a и b), а целые числа x, y — коэффициентами Безу.

Пример

НОД$(12, 30) = 6.$ Соотношение Безу имеет вид:

$6=3 \cdot 12 + (-1) \cdot 30$

Следствие

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

$ax+by=1$

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

Свойства

• НОД$(a, b)$ является наименьшим натуральным числом, которое может быть представлено в виде линейной комбинации чисел a и b с целыми коэффициентами.
• Для практического вычисления коэффициентов $x, y$ можно использовать алгоритм Евклида. Его последний шаг связывает НОД с промежуточными остатками от деления, которые, если по очереди подставить все их значения из вышележащих строк, свяжут НОД непосредственно с первоначальными числами.
• Коэффициенты Безу $x, y$ определены неоднозначно — если какие-то их значения известны, то всё множество коэффициентов даётся формулой:

  $\left\{ \left(x+\frac{kb}{d},\ y-\frac{ka}{d}\right) \mid k \in \mathbb{Z} \right\},$

где d = НОД(a, b).

Обобщения

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

Пусть $a_1$, …, $a_n$ — целые числа, не все равные нулю. Тогда существуют такие целые числа $x_1$, …, $x_n$, что выполняется соотношение: НОД$(a_1$, …, $a_n)$ = $x_1\cdot a_1 + \cdots x_n\cdot a_n$

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

Пусть $\left(P_i\right)_{i\in I}$ — какое-либо семейство многочленов, и не все они равны нулю. Обозначим $\Delta$ их наибольший общий делитель. Тогда существует такое семейство многочленов $\left(A_i\right)_{i\in I}$, что выполняется соотношение: $\Delta = \sum_{i\in I} A_iP_i$

История

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

См. также

• Алгоритм Евклида

Примечания

1. ↑ 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.

Литература

• Виноградов И. М. Основы теории чисел. М.-Л.: Гос. изд. технико-теоретической литературы, 1952, 180 с.
• Калужнин Л. А. Основная теорема арифметики. — М.: Наука, 1969. — (Популярные лекции по математике).

Ссылки

• Онлайн-калькулятор коэффициентов соотношения Безу.