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

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

История

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

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

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

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

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

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

Пусть ${\displaystyle a}$ , ${\displaystyle b}$ — натуральные числа. Тогда существуют такие натуральные числа ${\displaystyle x,y}$ , что выполняется соотношение НОД ${\displaystyle (a,b)=x\cdot a-y\cdot b}$

Примеры

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

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

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

Следствия

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

${\displaystyle ax+by=1}$

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

НОД ${\displaystyle (a,b)}$ является наименьшим натуральным числом, которое может быть представлено в виде линейной комбинации чисел ${\displaystyle a}$ и ${\displaystyle b}$ с целыми коэффициентами .

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

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

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

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

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

${\displaystyle ax+by=d,}$ где ${\displaystyle d=}$ НОД ${\displaystyle (a,b).}$

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

${\displaystyle {\frac {a}{d}}x+{\frac {b}{d}}y=1.}$

Отсюда следует, что коэффициенты Безу ${\displaystyle x,y}$ определены неоднозначно — если какие-то их значения ${\displaystyle x_{0},y_{0}}$ известны, то всё множество коэффициентов даётся формулой

${\displaystyle \left\{\left(x_{0}+{\frac {kb}{d}},y_{0}-{\frac {ka}{d}}\right)\mid k=0,\pm 1,\pm 2,\pm 3\dots \right\}.}$

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

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

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

${\displaystyle r_{1}=a-bq_{0},}$

${\displaystyle r_{2}=b-r_{1}q_{1}=b-(a-bq_{0})q_{1}=b(1+q_{0}q_{1})-aq_{1},}$

${\displaystyle r_{3}=r_{1}-r_{2}q_{2}=(a-bq_{0})-(b(1+q_{0}q_{1})-aq_{1})q_{2}=a(1+q_{1}q_{2})-b(q_{0}+q_{2}+q_{0}q_{1}q_{2}),}$

…

${\displaystyle r_{n}=r_{n-2}-r_{n-1}q_{n-1}=\dots =ax+by.}$

Пример

Найдём соотношение Безу для ${\displaystyle a=991,b=981.}$ Формулы алгоритма Евклида имеют вид

${\displaystyle 991={\boldsymbol {981}}\cdot 1+10,}$

${\displaystyle {\boldsymbol {981}}=10\cdot 98+1,}$

${\displaystyle 10=1\cdot 10.}$

Таким образом, НОД ${\displaystyle (991,981)=1}$ . Из этих формул получаем:

${\displaystyle 10={\boldsymbol {991}}-1\cdot {\boldsymbol {981}},}$

${\displaystyle 1={\boldsymbol {981}}-10\cdot 98={\boldsymbol {981}}-98\cdot ({\boldsymbol {991}}-{\boldsymbol {981}})=99\cdot {\boldsymbol {981}}-98\cdot {\boldsymbol {991}}.}$

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

${\displaystyle 1=99\cdot {\boldsymbol {981}}-98\cdot {\boldsymbol {991}}.}$

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

Альтернативный (по существу эквивалентный) способ решения уравнения ${\displaystyle ax+by=d}$ использует непрерывные дроби . Разделим обе части уравнения на НОД: ${\displaystyle a_{1}x+b_{1}y=1}$ . Далее разложим ${\displaystyle {\frac {|a_{1}|}{|b_{1}|}}}$ в непрерывную дробь и подсчитаем подходящие дроби ${\displaystyle {\frac {p_{k}}{q_{k}}}}$ . Последняя ( ${\displaystyle n}$ -я) из них будет равна ${\displaystyle {\frac {|a_{1}|}{|b_{1}|}}}$ и связана с предыдущей обычным соотношением:

${\displaystyle p_{n}q_{n-1}-q_{n}p_{n-1}=(-1)^{n-1}.}$

Подставив в эту формулу ${\displaystyle p_{n}=a_{1};q_{n}=b_{1}}$ и умножив обе части на ${\displaystyle d}$ , получаем

${\displaystyle aq_{n-1}-bp_{n-1}=\pm d.}$

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

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

Приведённый в предыдущем разделе алгоритм через непрерывные дроби, как и эквивалентный ему алгоритм Евклида, даёт в результате пару ${\displaystyle (x,y)}$ , удовлетворяющую неравенствам

${\displaystyle |x|<\left|{\frac {b}{d}}\right|;\quad |y|<\left|{\frac {a}{d}}\right|.}$

Этот факт следует из того, что дроби ${\displaystyle {\frac {|y|}{|x|}}}$ и ${\displaystyle {\frac {|a_{1}|}{|b_{1}|}}}$ , как указано выше, образуют последовательные подходящие дроби , а числитель и знаменатель следующей подходящей дроби всегда больше, чем у предыдущей . Для краткости можно назвать такую пару минимальной , таких пар всегда две.

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

${\displaystyle {\begin{alignedat}{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{alignedat}}}$

Применение

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

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

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

${\displaystyle ax+by=c.}$

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

${\displaystyle ax+by=d.}$

Тогда решением исходного уравнения будет пара ${\displaystyle c_{1}x,c_{1}y}$ , где ${\displaystyle c_{1}=c/d}$ .

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

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

${\displaystyle ax\equiv b{\pmod {m}}}$

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

${\displaystyle ax+my=b.}$

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

${\displaystyle ax\equiv 1{\pmod {m}}.}$

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

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

Пусть ${\displaystyle a_{1}}$ , …, ${\displaystyle a_{n}}$ — целые числа, не все равные нулю. Тогда существуют такие целые числа ${\displaystyle x_{1}}$ , …, ${\displaystyle x_{n}}$ , что выполняется соотношение: НОД ${\displaystyle (a_{1}}$ , …, ${\displaystyle a_{n})}$ = ${\displaystyle x_{1}\cdot a_{1}+\cdots +x_{n}\cdot a_{n}}$

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

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

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

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

Пусть даны многочлены ${\displaystyle f(x)}$ и ${\displaystyle g(x)}$ с коэффициентами в некотором поле. Тогда многочлены ${\displaystyle a(x)}$ и ${\displaystyle b(x)}$ такие, что ${\displaystyle af+bg=1}$ , существуют тогда и только тогда, когда ${\displaystyle f(x)}$ и ${\displaystyle g(x)}$ не имеют общих корней ни в каком алгебраически замкнутом поле (обычно в качестве последнего берётся поле комплексных чисел ).

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

См. также

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

Примечания

Литература

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

Ссылки

• коэффициентов соотношения Безу.
• (англ.) .
• (англ.) .

Эта статья входит в число добротных статей русскоязычного раздела Википедии.