Соотношение Безу
|
Соотношение Безу — представление наибольшего общего делителя целых чисел в виде их линейной комбинации с целыми коэффициентами. Названо в честь французского математика Этьена Безу. ИсторияВпервые данный факт опубликовал в 1624 году французский математик Клод Гаспар Баше де Мезириак для случая взаимно простых чисел. Этьен Безу в конце XVIII века обобщил теорему, распространив её на кольцо многочленов. ФормулировкаЭто утверждение называется соотношением Безу (для чисел a {displaystyle a} и b {displaystyle b} ), а также леммой Безу или тождеством Безу. При этом целые числа x , y {displaystyle x,y} называются коэффициентами Безу. Существует также модификация соотношения Безу, ограниченная натуральными числами: Примеры
СледствияЕсли числа 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}}.}Вариации и обобщенияСоотношение Безу легко обобщается на случай, когда имеется более двух чисел: Соотношение Безу может иметь место не только для целых чисел, но и в других коммутативных кольцах (например, для гауссовых целых чисел). Такие кольца называются кольцами Безу. Пример: формулировка для кольца многочленов (от одной переменной): Коэффициенты Безу для двух многочленов от одной переменной могут быть вычислены аналогично изложенному выше для целых чисел (с помощью расширенного алгоритма Евклида). Общие корни двух многочленов являются корнями также и их наибольшего общего делителя, поэтому из соотношения Безу и основной теоремы алгебры вытекает следующий результат: Обобщением этого результата на любое количество многочленов и неизвестных является Теорема Гильберта о нулях. |
