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

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

19.12.2020


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

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

История

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

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

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

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

Примеры

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

Следствия

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

a x + b y = 1 {displaystyle ax+by=1}

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

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

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

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

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

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

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

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

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

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

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

{ ( x 0 + k b d , y 0 − k a d ) ∣ k = 0 , ± 1 , ± 2 , ± 3 … } . {displaystyle left{left(x_{0}+{frac {kb}{d}},y_{0}-{frac {ka}{d}} ight)mid k=0,pm 1,pm 2,pm 3dots ight}.}

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

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

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

r 1 = a − b q 0 , {displaystyle r_{1}=a-bq_{0},} r 2 = b − r 1 q 1 = b − ( a − b q 0 ) q 1 = b ( 1 + q 0 q 1 ) − a q 1 , {displaystyle r_{2}=b-r_{1}q_{1}=b-(a-bq_{0})q_{1}=b(1+q_{0}q_{1})-aq_{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 ) , {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}),} … r n = r n − 2 − r n − 1 q n − 1 = ⋯ = a x + b y . {displaystyle r_{n}=r_{n-2}-r_{n-1}q_{n-1}=dots =ax+by.} Пример

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

991 = 981 ⋅ 1 + 10 , {displaystyle 991={oldsymbol {981}}cdot 1+10,} 981 = 10 ⋅ 98 + 1 , {displaystyle {oldsymbol {981}}=10cdot 98+1,} 10 = 1 ⋅ 10. {displaystyle 10=1cdot 10.}

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

10 = 991 − 1 ⋅ 981 , {displaystyle 10={oldsymbol {991}}-1cdot {oldsymbol {981}},} 1 = 981 − 10 ⋅ 98 = 981 − 98 ⋅ ( 991 − 981 ) = 99 ⋅ 981 − 98 ⋅ 991 . {displaystyle 1={oldsymbol {981}}-10cdot 98={oldsymbol {981}}-98cdot ({oldsymbol {991}}-{oldsymbol {981}})=99cdot {oldsymbol {981}}-98cdot {oldsymbol {991}}.}

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

1 = 99 ⋅ 981 − 98 ⋅ 991 . {displaystyle 1=99cdot {oldsymbol {981}}-98cdot {oldsymbol {991}}.}

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

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

p n q n − 1 − q n p n − 1 = ( − 1 ) n − 1 . {displaystyle p_{n}q_{n-1}-q_{n}p_{n-1}=(-1)^{n-1}.}

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

a q n − 1 − b p n − 1 = ± d . {displaystyle aq_{n-1}-bp_{n-1}=pm d.}

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

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

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

| x | < | b d | ; | y | < | a d | . {displaystyle |x|<left|{frac {b}{d}} ight|;quad |y|<left|{frac {a}{d}} ight|.}

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

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

… 12 × − 10 + 42 × 3 = 6 12 × − 3 + 42 × 1 = 6 12 × 4 + 42 × − 1 = 6 12 × 11 + 42 × − 3 = 6 12 × 18 + 42 × − 5 = 6 … {displaystyle {egin{alignedat}{3}&dots &12 imes &color {blue}{-10}&{}+42 imes &color {blue}{3}&{}=6&12 imes &color {red}{-3}&{}+42 imes &color {red}{1}&{}=6&12 imes &color {red}{4}&{}+42 imes &color {red}{-1}&{}=6&12 imes &color {blue}{11}&{}+42 imes &color {blue}{-3}&{}=6&12 imes &color {blue}{18}&{}+42 imes &color {blue}{-5}&{}=6&dots end{alignedat}}}

Применение

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

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

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

a x + b y = c . {displaystyle ax+by=c.}

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

a x + b y = d . {displaystyle ax+by=d.}

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

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

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

a x ≡ b ( mod m ) {displaystyle axequiv b{pmod {m}}}

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

a x + m y = b . {displaystyle ax+my=b.}

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

a x ≡ 1 ( mod m ) . {displaystyle axequiv 1{pmod {m}}.}

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

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

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

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

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

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