Русская Википедия:Соотношение Безу

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

История

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

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

Формулировка

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

НОД<math>(a, b) = x \cdot a + y \cdot b</math>

|} Это утверждение называется соотношением Безу (для чисел <math>a</math> и <math>b</math>), а также леммой Безу или тождеством Безу. При этом целые числа <math>x, y</math> называются коэффициентами Безу.

Существует также модификация соотношения Безу, ограниченная натуральными числами: Шаблон:Рамка Пусть <math>a</math>, <math>b</math> — натуральные числа. Тогда существуют такие натуральные числа <math>x, y</math>, что выполняется соотношение

НОД<math>(a, b) = x \cdot a - y \cdot b</math>

|}

Примеры

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

  <math>6=3 \cdot 12 + (-1) \cdot 30</math>

  • Возможны и другие варианты разложения НОД, например: <math>6=(-2) \cdot 12 + 1 \cdot 30.</math>

Следствия

Если числа <math>a, b</math> взаимно простые, то уравнение

<math>ax + by = 1</math>

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

НОД<math>(a, b)</math> является наименьшим натуральным числом, которое может быть представлено в виде линейной комбинации чисел <math>a</math> и <math>b</math> с целыми коэффициентами.

Множество целочисленных линейных комбинаций <math>\{ax + by\}</math> совпадает с множеством кратных для НОД<math>(a,b)</math>).

Коэффициенты Безу

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

Неоднозначность

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

<math>a x + b y = d, </math> где <math>d=</math> НОД<math>(a, b).</math>

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

<math>\frac{a}{d} x + \frac{b}{d} y = 1.</math>

Отсюда следует, что коэффициенты Безу <math>x, y</math> определены неоднозначно — если какие-то их значения <math>x_0, y_0</math> известны, то всё множество коэффициентов даётся формулой

<math> \left\{ \left(x_0 + \frac{kb}{d}, y_0 - \frac{ka}{d}\right) \mid k = 0, \pm 1, \pm 2, \pm 3 \dots \right\}.</math>

Ниже будет показаноШаблон:Переход, что существуют коэффициенты Безу, удовлетворяющие неравенствам <math>|x| < \left|\frac{b}{d}\right|</math> и <math>|y| < \left|\frac{a}{d}\right|</math>.

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

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

<math>r_1 = a - bq_0,</math>

<math>r_2 = b - r_1q_1 = b - (a - bq_0)q_1 = b(1 + q_0q_1) - aq_1,</math>

<math>r_3 = r_1 - r_2q_2 = (a - bq_0) - (b(1 + q_0q_1) - aq_1)q_2 = a(1 + q_1q_2) - b(q_0 + q_2 + q_0q_1q_2),</math>

…

<math>r_n = r_{n-2} - r_{n-1}q_{n-1} = \dots = ax + by.</math>

Пример

Найдём соотношение Безу для <math>a = 991, b = 981.</math> Формулы алгоритма Евклида имеют вид

<math>991 = \boldsymbol{981} \cdot 1 + 10,</math>

<math>\boldsymbol{981} = 10 \cdot 98 + 1,</math>

<math>10 = 1 \cdot 10.</math>

Таким образом, НОД<math>(991, 981) = 1</math>. Из этих формул получаем:

<math>10 = \boldsymbol{991} - 1 \cdot \boldsymbol{981},</math>

<math>1 = \boldsymbol{981} - 10 \cdot 98 = \boldsymbol{981} - 98 \cdot (\boldsymbol{991} - \boldsymbol{981}) = 99 \cdot \boldsymbol{981} - 98 \cdot \boldsymbol{991}.</math>

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

<math>1 = 99 \cdot \boldsymbol{981} - 98 \cdot \boldsymbol{991}.</math>

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

Альтернативный (по существу эквивалентный) способ решения уравнения <math>a x + b y = d </math> использует непрерывные дроби. Разделим обе части уравнения на НОД: <math>a_1 x + b_1 y = 1</math>. Далее разложим <math>\frac{|a_1|}{|b_1|}</math> в непрерывную дробь и подсчитаем подходящие дроби <math>\frac{p_k}{q_k}</math>. Последняя (<math>n</math>-я) из них будет равна <math>\frac{|a_1|}{|b_1|}</math> и связана с предыдущей обычным соотношением:

<math>p_n q_{n-1} - q_n p_{n-1} = (-1)^{n-1}.</math>

Подставив в эту формулу <math>p_n = a_1; q_n = b_1</math> и умножив обе части на <math>d</math>, получаем

<math>a q_{n-1} - b p_{n-1} = \pm d.</math>

С точностью до знака, это соотношение Безу. поэтому предпоследняя подходящая дробь <math>\frac{p_{n-1}}{q_{n-1}}</math> даёт модули решения: <math>|x|</math> есть знаменатель этой дроби, а <math>|y|</math> — числитель. Осталось, исходя из первоначального уравнения, найти знаки <math>x, y</math>; для этого достаточно найти последние цифры в произведениях <math>|ax|, |by|</math>.

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

Приведённый в предыдущем разделе алгоритм через непрерывные дроби, как и эквивалентный ему алгоритм Евклида, даёт в результате пару <math>(x,y)</math>, удовлетворяющую неравенствам

<math>|x| < \left|\frac{b}{d}\right|; \quad |y| < \left|\frac{a}{d}\right|.</math>

Этот факт следует из того, что дроби <math>\frac{|y|}{|x|}</math> и <math>\frac{|a_1|}{|b_1|}</math>, как указано выше, образуют последовательные подходящие дроби, а числитель и знаменатель следующей подходящей дроби всегда больше, чем у предыдущей. Для краткости можно назвать такую пару минимальной, таких пар всегда две.

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

<math>

\begin{alignat}{3} &\dots \\ &12 \times &\color{blue}{-10} &{}+ 42 \times &\color{blue}{3} &{}= 6 \\ &12 \times &\color{red}{-3} &{}+ 42 \times &\color{red}{1} &{}= 6 \\ &12 \times &\color{red}{4} &{}+ 42 \times &\color{red}{-1} &{}= 6 \\ &12 \times &\color{blue}{11} &{}+ 42 \times &\color{blue}{-3} &{}= 6 \\ &12 \times &\color{blue}{18} &{}+ 42 \times &\color{blue}{-5} &{}= 6 \\ &\dots \end{alignat} </math>

Применение

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

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

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

<math>ax + by = c.</math>

Обозначим <math>d = {}</math>НОД<math>(a, b).</math> Очевидно, уравнение имеет целочисленные решения только в том случае, когда <math>c</math> делится на <math>d</math>. Будем считать это условие выполненным, и одним из приведённых выше алгоритмов найдём коэффициенты Безу <math>x, y</math>:

<math>ax + by = d.</math>

Тогда решением исходного уравнения будет пара <math>c_1 x, c_1 y</math>, где <math>c_1 = c / d</math>.

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

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

<math>ax \equiv b \pmod m</math>

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

<math>ax + my = b.</math>

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

<math>ax \equiv 1 \pmod m.</math>

Вариации и обобщения

Соотношение Безу легко обобщается на случай, когда имеется более двух чисел: Шаблон:Рамка Пусть <math>a_1</math>, …, <math>a_n</math> — целые числа, не все равные нулю. Тогда существуют такие целые числа <math>x_1</math>, …, <math>x_n</math>, что выполняется соотношение:

НОД<math>(a_1</math>, …, <math>a_n)</math> = <math>x_1\cdot a_1 + \cdots + x_n\cdot a_n</math>

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

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

<math>\Delta = \sum_{i\in I} A_iP_i</math>

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

Шаблон:Рамка Пусть даны многочлены <math>f(x)</math> и <math>g(x)</math> с коэффициентами в некотором поле. Тогда многочлены <math>a(x)</math> и <math>b(x)</math> такие, что <math>af + bg = 1</math>, существуют тогда и только тогда, когда <math>f(x)</math> и <math>g(x)</math> не имеют общих корней ни в каком алгебраически замкнутом поле (обычно в качестве последнего берётся поле комплексных чисел). Шаблон:Конец рамки

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

См. также

• Алгоритм Евклида
• Диофантово уравнение
• Наибольший общий делитель
• Решение сравнений
• Сравнение по модулю

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга

Ссылки

• Онлайн-калькулятор коэффициентов соотношения Безу.
• Bezout’s Identity Шаблон:Ref-en.
• Bezout’s identity, Euclidean algorithmШаблон:Ref-en.