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

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

История


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

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


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

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

Примеры



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

Следствия


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

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

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


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

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


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

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

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

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

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


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


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

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

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

1=9998198991

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


 Альтернативный (по существу эквивалентный) способ решения уравнения ax+by=d использует непрерывные дроби. Разделим обе части уравнения на НОД: 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=±d
  С точностью до знака, это соотношение Безу. поэтому предпоследняя подходящая дробь pn1qn1 даёт модули решения: |x| есть знаменатель этой дроби, а |y| — числитель. Осталось, исходя их первоначального уравнения, найти знаки x,y; для этого достаточно найти последние цифры в произведениях |ax|,|by|.

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


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

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

ax+by=d
  Тогда решением исходного уравнения будет пара 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) не имеют общих корней ни в каком алгебраически замкнутом поле (обычно в качестве последнего берётся поле комплексных чисел).
 Обобщением этого результата на любое количество многочленов и неизвестных является Теорема Гильберта о нулях.