xy=yx

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

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

История


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

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


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

 НОД(a,b)=xa+yb,(a,b)=xa+yb,
 которое называется соотношением Безу (для чисел aa и bb), атакже леммой Безу или тождеством Безу. При этом целыечисла x,yx,y называются коэффициентами Безу.

Примеры



  • НОД(12,30)=6.(12,30)=6. Соотношение Безу имеет вид:
    6=312+(1)306=312+(1)30
    • Возможны и другие варианты разложения НОД, например: 6=(2)12+130.6=(2)12+130.

Следствия


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

ax+by=1ax+by=1
 имеет целочисленные решения. Этот важный факт облегчает решениедиофантовых уравнений первого порядка.
 НОД(a,b)(a,b) является наименьшим натуральным числом, которое может бытьпредставлено в виде линейной комбинации чисел aa и bb с целымикоэффициентами.
 Множество целочисленных линейных комбинаций {ax+by}{ax+by} совпадает смножеством кратных для НОД(a,b)(a,b)).

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


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

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


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

ax+by=d,ax+by=d, где d=d= НОД(a,b).(a,b).
 Или, что то же самое:

ad x+bd y=1ad x+bd y=1
 Отсюда следует, что коэффициенты Безу x,yx,y определены неоднозначно —если какие-то их значения x0.y0x0.y0 известны, то всё множествокоэффициентов даётся формулой:

{(x0+kbd, y0kad)k=0,±1,±2,±3}{(x0+kbd, y0kad)k=0,±1,±2,±3}
 Ниже будет показано, что существуют коэффициенты Безу, удовлетворяющиенеравенствам |x|<|bd||x|<bd и|y|<|ad|.|y|<ad.

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


 Для нахождения коэффициентов Безу можно использовать расширенныйалгоритм Евклида нахождения НОД и представить остатки в виде линейныхкомбинаций a и b. Шаги алгоритма записываются в следующемвиде:
r1=abq0r1=abq0
r2=br1q1=b(abq0)q1=b(1+q0q1)aq1r2=br1q1=b(abq0)q1=b(1+q0q1)aq1
r3=r1r2q2=(abq0)(b(1+q0q1)aq1)q2=a(1+q1q2)b(q0+q2+q0q1q2)r3=r1r2q2=(abq0)(b(1+q0q1)aq1)q2=a(1+q1q2)b(q0+q2+q0q1q2)
 \ldots
rn=rn2rn1qn1==ax+by.rn=rn2rn1qn1==ax+by.


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

991=9811+10991=9811+10
981=1098+1981=1098+1
10=11010=110
 Таким образом, НОД(991,981)=1.(991,981)=1. Из этих формул получаем:

10=991198110=9911981
1=9811098=98198(991981)=99981989911=9811098=98198(991981)=9998198991
 В итоге соотношение Безу имеет вид:

1=99981989911=9998198991

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


 Альтернативный (по существу эквивалентный) способ решения уравненияax+by=dax+by=d использует непрерывные дроби. Разделим обе частиуравнения на НОД: a1x+b1y=1.a1x+b1y=1. Далее разложим $\frac{|: p_n q_{n-1} - q_n p_{n-1} = (-1)^{n-1}ПодставиввэтуформулуПодставиввэтуформулуp_n =a_1;\ q_n =b_1иумноживобечастинаиумноживобечастинаd,$ получаем:

aqn1bpn1=±daqn1bpn1=±d
 С точностью до знака, это соотношение Безу. поэтому предпоследняяподходящая дробь pn1qn1pn1qn1 даёт модули решения: |x||x|есть знаменатель этой дроби, а |y||y| — числитель. Осталось, исходя ихпервоначального уравнения, найти знаки x,y;x,y; для этого достаточнонайти последние цифры в произведениях |ax|,|by||ax|,|by|.

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


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

|x|<|bd|;|y|<|ad||x|<bd;|y|<ad
 Этот факт следует из того, что дроби $\frac{|
 Пример. Пусть a=12, b=42.$ НОД (12, 42) = 6. Ниже приведенынекоторые элементы списка пар коэффициентов Безу, причём минимальныепары выделены красным цветом.


 \{begin\{align\} \{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\{align\}

Применение


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

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


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

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

ax+by=dax+by=d
 Тогда решением исходного уравнения будет пара c1x,c1y,c1x,c1y, гдеc1=c/d.

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


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

axb(modm).
 его достаточно преобразовать к виду:

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

ax1(modm).

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


 Соотношение Безу легко обобщается на случай, когда имеется более двухчисел: Пусть a1, \ldots, an — целые числа, не все равные нулю.Тогда существуют такие целые числа x1, \ldots, xn, чтовыполняется соотношение:

 НОД(a1, \ldots, an) = x1a1+xnan
 Соотношение Безу может иметь место не только для целых чисел, но и вдругих коммутативных кольцах (например, для гауссовых целых чисел).Такие кольца называются кольцами Безу.
 Пример: формулировка для кольца многочленов (от одной переменной): Пусть(Pi)iI — какое-либо семейство многочленов, и невсе они равны нулю. Обозначим Δ их наибольший общий делитель.Тогда существует такое семейство многочленов(Ai)iI, что выполняется соотношение:

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