Личность Безу

В элементарной теории чисел , соотношение безу (также называемая лемма Безу ) является следующая теорема :

Соотношение беза - Пусть и б быть целыми числами с наибольшим общим делителем д . Тогда существуют целые числа x и y такие, что ax + by = d . В более общем смысле, целые числа в форме ax + by в точности кратны d .

Здесь наибольший общий делитель 0 и 0 взят равным 0. Целые числа x и y называются коэффициентами Безу для ( a , b ); они не уникальны. Пара коэффициентов Безу может быть вычислена с помощью расширенного алгоритма Евклида , и эта пара является одной из двух пар таких, что ${\ Displaystyle | х | \ Leq | б / д |}$ а также ${\ Displaystyle | у | \ leq | а / д |}$ . Равенство может иметь место только в том случае, если одно из a и b кратно другому.

Например, наибольший общий делитель 15 и 69 равен 3, и можно записать 15 × (-9) + 69 × 2 = 3 .

Многие другие теоремы элементарной теории чисел, такие как лемма Евклида или китайская теорема об остатках , являются результатом тождества Безу.

Безу домен является областью целостности , в которой имеет место соотношение беза. В частности, тождество Безу выполняется в областях главных идеалов . Таким образом, каждая теорема, вытекающая из тождества Безу, верна во всех этих областях.

Структура решений

Если $a$ и $b$ одновременно не равны нулю и была вычислена одна пара коэффициентов Безу $(x, y)$ (например, с использованием расширенного алгоритма Евклида ), все пары могут быть представлены в виде

{\ displaystyle \ left (xk {\ frac {b} {d}}, \ y + k {\ frac {a} {d}} \ right),}

где $k$ - произвольное целое число, $d$ - наибольший общий делитель $a$ и $b$ , а дроби упрощаются до целых чисел.

Если $a$ и $b$ оба ненулевые, то ровно две из этих пар пар коэффициентов Безу удовлетворяют

{\ displaystyle | x | \ leq \ left | {\ frac {b} {d}} \ right | \ quad {\ text {and}} \ quad | y | \ leq \ left | {\ frac {a} { d}} \ right |,}

и равенство может иметь место, только если одно из $a$ и $b$ делит другое.

Это основано на свойстве евклидова деления : для двух ненулевых целых чисел $c$ и $d$ , если $d$ не делит $c$ , существует ровно одна пара $(q, r)$ такая, что $c = dq + r$ и $0 < r <| d |$ , и еще один такой, что $c = dq + r$ и $- | d | < г <0$ .

Две пары малых коэффициентов Безу получаются из заданного $(x, y)$ путем выбора в качестве $k$ в приведенной выше формуле любого из двух целых чисел рядом с ${\ displaystyle {\ frac {x} {b / d}}}$ .

Расширенный алгоритм Евклида всегда производит одну из этих двух минимальных пар.

Пример

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

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

Если $(x, y) = (18, -5)$ - исходная пара коэффициентов Безу, то ${\ displaystyle {\ frac {18} {42/6}} \ in [2,3]}$ дает минимальные пары через $k = 2$ , соответственно $k = 3$ ; то есть $(18-2 7, -5 + 2 2) = (4, -1)$ и $(18-3 7, -5 + 3 \cdot 2) = (-3, 1)$ .

Доказательство

Для любых ненулевых целых чисел $a$ и $b$ пусть ${\ displaystyle S = \ {ax + by \ mid x, y \ in \ mathbb {Z} {\ text {and}} ax + by> 0 \}.}$ Множество $S$ непусто, поскольку содержит либо $a,$ либо $- a$ (при $x = \pm 1$ и $y = 0$ ). Поскольку $S$ - непустое множество натуральных чисел, он имеет минимальный элемент ${\ displaystyle d = as + bt}$ , по принципу хорошего порядка . Для того, чтобы доказать , что $d$ наибольший общий делитель и $Ь$ , оно должно быть доказано , что $d$ является общим делителем и $б$ , и что для любой другой общий делитель $с$ , один имеет $гр$ $\leq$ $d$ .

Евклидово деление на от $д$ может быть записана

{\ displaystyle a = dq + r \ quad {\ text {with}} \ quad 0 \ leq r }>

Остаток $r$ находится в ${\ Displaystyle S \ чашка \ {0 \}}$ , так как

{\ displaystyle {\ begin {align} r & = a-qd \\ & = aq (as + bt) \\ & = a (1-qs) -bqt. \ end {align}}}

Таким образом, $r$ имеет вид ${\ displaystyle ax + by}$ , и поэтому ${\ Displaystyle г \ в С \ чашка \ {0 \}}$ . Однако $0 \leq r < d$ , и $d$ является наименьшим положительным целым числом в $S$ : остаток $r не$ может быть в $S$ , поэтому $r$ обязательно 0. Это означает, что $d$ является делителем $a$ . Точно так же $d$ также является делителем $b$ , а $d$ является общим делителем $a$ и $b$ .

Пусть теперь $c$ - любой общий делитель $a$ и $b$ ; то есть существуют такие $u$ и $v$ , что $a = cu$ и $b = cv$ . Таким образом

{\ displaystyle {\ begin {align} d & = as + bt \\ & = cus + cvt \\ & = c (us + vt). \ end {align}}}

То есть $c$ является делителем $d$ и, следовательно, $c \leq d.$

Обобщения

Для трех и более целых чисел

Личность Безу может быть расширена до более чем двух целых чисел: если

{\ displaystyle \ gcd (a_ {1}, a_ {2}, \ ldots, a_ {n}) = d}

тогда есть целые числа ${\ Displaystyle x_ {1}, x_ {2}, \ ldots, x_ {n}}$ такой, что

{\ displaystyle d = a_ {1} x_ {1} + a_ {2} x_ {2} + \ cdots + a_ {n} x_ {n}}

обладает следующими свойствами:

d - наименьшее натуральное число этой формы
каждое число в этой форме кратно d

Для полиномов

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

Поскольку общие корни двух многочленов являются корнями их наибольшего общего делителя, тождество Безу и основная теорема алгебры влекут следующий результат:

Для одномерных многочленов f и g с коэффициентами в поле существуют многочлены a и b такие, что af + bg = 1 тогда и только тогда, когда f и g не имеют общего корня в любом алгебраически замкнутом поле (обычно поле комплексных чисел ).

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

Для основных идеальных областей

Как отмечалось во введении, тождество Безу работает не только в кольце целых чисел, но и в любой другой области главных идеалов (PID). То есть, если R - PID, а a и b - элементы R , а d - наибольший общий делитель a и b , то есть элементы x и y в R такие, что ax + by = d . Причина в том, что идеал Ra + Rb является главным и равен Rd .

Область целостности, в которой выполняется тождество Безу, называется областью Безу .

История

Французский математик Этьен Безу (1730–1783) доказал это тождество для многочленов. ^[1] Однако это утверждение для целых чисел можно найти уже в работе другого французского математика, Клода Гаспара Баше де Мезириак (1581–1638). ^[2]^[3]^[4]

Смотрите также

Теорема AF + BG , аналог тождества Безу для однородных многочленов от трех неопределенных
Основная теорема арифметики
Лемма евклида

Заметки

^ Безу, É. (1779). Théorie générale des équations algébriques . Париж, Франция: Ph.-D. Пьер.
^ Тиньоль, Жан-Пьер (2001). Теория Галуа алгебраических уравнений . Сингапур: World Scientific. ISBN 981-02-4541-6.
^ Клод Гаспар Баше (сье де Мезириак) (1624). Problèmes plaisants & délectables qui se font par les nombres (2-е изд.). Лион, Франция: Pierre Rigaud & Associates. С. 18–33.На этих страницах Баше доказывает (без уравнений) «Предложение XVIII. Deux nombres premiers entre eux estant donnez, treuver le moindre multiple de chascun d'iceux, surpassant de l'unité un multiple de l'autre». (Для двух чисел, [которые] взаимно просты, найдите наименьшее кратное каждого из них [такое, чтобы] одно кратное превышало другое на единицу (1).) Эта задача (а именно, ax - by = 1) является частным случаем уравнения Безу и использовался Баше для решения задач, представленных на страницах 199 и далее.
^ См. Также: Маартен Буллинк (февраль 2009 г.). "Модульная арифметика перед К. Ф. Гауссом: систематизация и обсуждение проблем остатка в Германии 18-го века" (PDF) . Historia Mathematica . 36 (1): 48–72. DOI : 10.1016 / j.hm.2008.08.009 .

Внешние ссылки

Онлайн-калькулятор личности Безу.
Вайсштейн, Эрик В. «Личность Безу» . MathWorld .

[1] Безу, É. (1779). Théorie générale des équations algébriques . Париж, Франция: Ph.-D. Пьер.

[2] Тиньоль, Жан-Пьер (2001). Теория Галуа алгебраических уравнений . Сингапур: World Scientific. ISBN 981-02-4541-6.

[3] Клод Гаспар Баше (сье де Мезириак) (1624). Problèmes plaisants & délectables qui se font par les nombres (2-е изд.). Лион, Франция: Pierre Rigaud & Associates. С. 18–33.На этих страницах Баше доказывает (без уравнений) «Предложение XVIII. Deux nombres premiers entre eux estant donnez, treuver le moindre multiple de chascun d'iceux, surpassant de l'unité un multiple de l'autre». (Для двух чисел, [которые] взаимно просты, найдите наименьшее кратное каждого из них [такое, чтобы] одно кратное превышало другое на единицу (1).) Эта задача (а именно, ax - by = 1) является частным случаем уравнения Безу и использовался Баше для решения задач, представленных на страницах 199 и далее.

[4] См. Также: Маартен Буллинк (февраль 2009 г.). "Модульная арифметика перед К. Ф. Гауссом: систематизация и обсуждение проблем остатка в Германии 18-го века" (PDF) . Historia Mathematica . 36 (1): 48–72. DOI : 10.1016 / j.hm.2008.08.009 .

[1]