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

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

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

История

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

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

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

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

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

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

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

НОД$(a,b)=x\cdot a-y\cdot b$

|}

Примеры

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

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

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

Следствия

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

$ax+by=1$

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

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

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

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

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

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

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

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

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

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

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

$\{(x_0+\frac{kb}{d},y_0-\frac{ka}{d})\mid k=0,\pm 1,\pm 2,\pm 3\dots \}.$

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

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

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

$r_1=a-b{q}_0,$

$r_2=b-r_1{q}_1=b-(a-b{q}_0)q_1=b(1+q_0{q}_1)-a{q}_1,$

$r_3=r_1-r_2{q}_2=(a-b{q}_0)-(b(1+q_0{q}_1)-a{q}_1)q_2=a(1+q_1{q}_2)-b(q_0+q_2+q_0{q}_1{q}_2),$

…

$r_n=r_{n-2}-r_{n-1}{q}_{n-1}=\dots =ax+by.$

Пример

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

$991=981\cdot 1+10,$

$981=10\cdot 98+1,$

$10=1\cdot 10.$

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

$10=991-1\cdot 981,$

$1=981-10\cdot 98=981-98\cdot (991-981)=99\cdot 981-98\cdot 991.$

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

$1=99\cdot 981-98\cdot 991.$

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

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

$p_n{q}_{n-1}-q_n{p}_{n-1}=(-1{)}^{n-1}.$

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

$a{q}_{n-1}-b{p}_{n-1}=\pm d.$

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

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

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

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

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

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

$\begin{array}{cc}& \dots \\ & 12\times & -10& +42\times & 3& =6\\ & 12\times & -3& +42\times & 1& =6\\ & 12\times & 4& +42\times & -1& =6\\ & 12\times & 11& +42\times & -3& =6\\ & 12\times & 18& +42\times & -5& =6\\ & \dots \end{array}$

Применение

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

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

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

$ax+by=c.$

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

$ax+by=d.$

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

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

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

$ax\equiv b(\mathrm{mod}m)$

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

$ax+my=b.$

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

$ax\equiv 1(\mathrm{mod}m).$

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

Соотношение Безу легко обобщается на случай, когда имеется более двух чисел: Шаблон:Рамка Пусть $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}$ — какое-либо семейство многочленов, и не все они равны нулю. Обозначим $\mathrm{\Delta }$ их наибольший общий делитель. Тогда существует такое семейство многочленов ${\left(A_i\right)}_{i\in I}$, что выполняется соотношение:

$\mathrm{\Delta }=\sum _{i\in I}{A}_i{P}_i$

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

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

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

См. также

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

Литература

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

Ссылки

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