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

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

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

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

НОД(a, b) = x \cdot a + y \cdot b.

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

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

Доказательство[править | править вики-текст]

Докажем по индукции :

Допустим, что :

a = bq_1 + r_1

b = r_1 q_2 + r_2

r_1 = r_2 q_3 + r_3

...

r_{n-2} = r_{n-1} q_n + r_n

Для n = 1 : r_1 = a - bq_1 предположим, что:

r_k = x_k a + y_k b для любого k = 1..n-1

Покажем что r_n = x_n a + y_n b

r_n = r_{n-2} - r_{n-1} q_n = (x_{n-2} a + y_{n-2} b) - (x_{n-1} a + y_{n-1} b)\cdot q_n = (x_{n-2} - x_{n-1} q_n) \cdot a + (y_{n-2} - y_{n-1} q_n) \cdot b = x_n a + y_n b

Откуда следует что : Существуют такие целые числа x, y что выполняется соотношение : НОД(a, b) = x \cdot a + y \cdot b.

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

НОД(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.

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

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