Просмотр кода страницы Соотношение Безу

'''Соотноше́ние Безу́''' — представление [[наибольший общий делитель|наибольшего общего делителя]] целых чисел в виде их [[линейная комбинация|линейной комбинации]] с целыми коэффициентами{{sfn |Хассе Г.|1953|с=29|name=HASSE}}.

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

== История ==
Впервые данный факт опубликовал в 1624 году французский математик [[Клод Гаспар Баше де Мезириак]] для случая взаимно простых чисел<ref>{{cite book |author=Claude Gaspard Bachet, sieur de Méziriac |chapter=Problèmes plaisants et délectables |title=Problemes plaisans, qui se font par nombres |edition=2nd ed |place=Lyons, France |publisher=Pierre Rigaud & Associates |year=1624 |pages=18-33 |url=http://www.bsb-muenchen-digital.de/~web/web1008/bsb10081407/images/index.html?digID=bsb10081407&pimage=38&v=100&nav=0&l=de}}</ref>. [[Этьен Безу]] в конце XVIII века обобщил теорему, распространив её на кольцо многочленов.

== Формулировка ==
{{рамка}}
Пусть <math>a</math>, <math>b</math> — [[Целое число|целые числа]], хотя бы одно из которых не нуль. Тогда существуют такие целые числа <math>x, y</math>, что выполняется соотношение
: НОД<math>(a, b) = x \cdot a + y \cdot b</math>
|}
Это утверждение называется '''соотношением Безу''' (для чисел <math>a</math> и <math>b</math>), а также ''леммой Безу'' или ''тождеством Безу''<ref>{{книга |автор=Jones, G. A., Jones, J. M.|часть=§1.2. Bezout's Identity|заглавие=Elementary Number Theory |место=Berlin |издательство=Springer-Verlag |год=1998|pages=7—11}}</ref>.
При этом целые числа <math>x, y</math> называются '''коэффициентами Безу'''.

Существует также модификация соотношения Безу, ограниченная [[Натуральное число|натуральными числами]]<ref>{{книга |автор=Дэвенпорт Г. |заглавие=Высшая арифметика. Введение в теорию чисел. |место=М.|издательство=Наука |год=1965 |страницы=28 |страниц=176 }}</ref>:
{{рамка}}
Пусть <math>a</math>, <math>b</math> — натуральные числа. Тогда существуют такие натуральные числа <math>x, y</math>, что выполняется соотношение
: НОД<math>(a, b) = x \cdot a - y \cdot b</math>
|}

== Примеры ==
*НОД<math>(12, 30) = 6.</math> Соотношение Безу имеет вид:
*: <math>6=3 \cdot 12 + (-1) \cdot 30</math>
**Возможны и другие варианты разложения НОД, например: <math>6=(-2) \cdot 12 + 1 \cdot 30.</math>

== Следствия ==
Если числа <math>a, b</math> [[взаимно простые числа|взаимно простые]], то уравнение
: <math>ax + by = 1</math>
имеет целочисленные решения{{sfn|Хассе Г.|1953|с=33}}. Этот важный факт облегчает решение [[Диофантово уравнение|диофантовых уравнений]] первого порядка.

НОД<math>(a, b)</math> является наименьшим натуральным числом, которое может быть представлено в виде линейной комбинации чисел <math>a</math> и <math>b</math> с целыми коэффициентами<ref>{{книга|автор=Фаддеев Д. К. |заглавие=Лекции по алгебре. Учебное пособие для вузов |издательство=Наука |год=1984|страницы=9|страниц=416}}</ref>.

Множество целочисленных линейных комбинаций <math>\{ax + by\}</math> совпадает с множеством [[Делимость|кратных]] для НОД<math>(a,b)</math>)<ref name=brill>{{cite web|url=https://brilliant.org/wiki/bezouts-identity/ |title=Bezout's identity |accessdate=2014-12-25}}</ref>.

== Коэффициенты Безу ==
Поскольку случай, когда хотя бы одно из чисел <math>a,b</math> равно нулю, тривиален, далее в этом разделе предполагается, что оба эти числа не равны нулю.

=== Неоднозначность ===
Нахождение коэффициентов Безу эквивалентно решению [[Диофантово уравнение|диофантового уравнения]] первого порядка с двумя неизвестными:
: <math>a x  + b y = d, </math> где <math>d=</math> НОД<math>(a, b).</math>
Или, что то же самое:
: <math>\frac{a}{d} x  + \frac{b}{d} y = 1.</math>
Отсюда следует, что коэффициенты Безу <math>x, y</math> определены неоднозначно — если какие-то их значения <math>x_0, y_0</math> известны, то всё множество коэффициентов даётся формулой<ref>{{книга|автор=Гельфонд А. О.|заглавие=Решение уравнений в целых числах |издательство=Наука |год=1983 |серия=Популярные лекции по математике, выпуск 8 |страницы=9—10 |страниц=63}}</ref>
: <math> \left\{ \left(x_0 + \frac{kb}{d}, y_0 - \frac{ka}{d}\right) \mid k = 0, \pm 1, \pm 2, \pm 3 \dots \right\}.</math>

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

=== Вычисление коэффициентов с помощью алгоритма Евклида ===
{{Викиучебник|Реализации алгоритмов/Расширенный алгоритм Евклида|Программные реализации расширенного алгорима Евклида}}

Для нахождения коэффициентов Безу можно использовать [[расширенный алгоритм Евклида]] нахождения НОД и представить остатки в виде линейных комбинаций ''a'' и ''b''<ref>{{книга|автор=[[Егоров, Дмитрий Фёдорович|Егоров Д. Ф.]] |заглавие=Элементы теории чисел|место=Москва—Петроград |издательство=Госиздат |год=1923 |страницы=14 |страниц=202}}</ref>. Шаги алгоритма записываются в следующем виде:

:<math>r_1 = a - bq_0,</math>
:<math>r_2 = b - r_1q_1 = b - (a - bq_0)q_1 = b(1 + q_0q_1) - aq_1,</math>
:<math>r_3 = r_1 - r_2q_2 = (a - bq_0) - (b(1 + q_0q_1) - aq_1)q_2 = a(1 + q_1q_2) - b(q_0 + q_2 + q_0q_1q_2),</math>
:…
:<math>r_n = r_{n-2} - r_{n-1}q_{n-1} = \dots = ax + by.</math>

; Пример
Найдём соотношение Безу для <math>a = 991, b = 981.</math> Формулы алгоритма Евклида имеют вид
: <math>991 = \boldsymbol{981} \cdot 1 + 10,</math>
: <math>\boldsymbol{981} = 10 \cdot 98 + 1,</math>
: <math>10 = 1 \cdot 10.</math>
Таким образом, НОД<math>(991, 981) = 1</math>. Из этих формул получаем:
: <math>10 = \boldsymbol{991} - 1 \cdot \boldsymbol{981},</math>
: <math>1 = \boldsymbol{981} - 10 \cdot 98 = \boldsymbol{981} - 98 \cdot (\boldsymbol{991} - \boldsymbol{981}) = 99 \cdot \boldsymbol{981} - 98 \cdot \boldsymbol{991}.</math>
В итоге соотношение Безу имеет вид
: <math>1 = 99 \cdot \boldsymbol{981} - 98 \cdot \boldsymbol{991}.</math>

=== Вычисление коэффициентов с помощью непрерывных дробей ===
Альтернативный (по существу эквивалентный) способ решения уравнения <math>a x + b y = d </math> использует [[непрерывные дроби]]. Разделим обе части уравнения на НОД: <math>a_1 x  + b_1 y = 1</math>. Далее разложим <math>\frac{|a_1|}{|b_1|}</math> в непрерывную дробь и подсчитаем [[Непрерывная дробь|подходящие дроби]] <math>\frac{p_k}{q_k}</math>. Последняя {{nobr|(<math>n</math>-я)}} из них будет равна <math>\frac{|a_1|}{|b_1|}</math> и связана с предыдущей обычным соотношением:
: <math>p_n q_{n-1} - q_n p_{n-1} = (-1)^{n-1}.</math>
Подставив в эту формулу <math>p_n = a_1; q_n = b_1</math> и умножив обе части на <math>d</math>, получаем
: <math>a q_{n-1} - b p_{n-1} = \pm d.</math>
С точностью до знака, это соотношение Безу. поэтому предпоследняя подходящая дробь <math>\frac{p_{n-1}}{q_{n-1}}</math> даёт модули решения: <math>|x|</math> есть знаменатель этой дроби, а <math>|y|</math> — числитель. Осталось, исходя из первоначального уравнения, найти знаки <math>x, y</math>; для этого достаточно найти последние цифры в произведениях <math>|ax|, |by|</math><ref name=SUSH>{{книга|автор=Сушкевич А. К.|заглавие=Теория чисел.  Элементарный курс|место=Харьков|издательство=Изд-во Харьковского университета|год=1954|страницы=49—51}}</ref>.

=== Минимальные пары коэффициентов ===
Приведённый в предыдущем разделе алгоритм через непрерывные дроби, как и эквивалентный ему алгоритм Евклида, даёт в результате пару <math>(x,y)</math>, удовлетворяющую неравенствам
: <math>|x| < \left|\frac{b}{d}\right|; \quad |y| < \left|\frac{a}{d}\right|.</math>
Этот факт следует из того, что дроби <math>\frac{|y|}{|x|}</math> и <math>\frac{|a_1|}{|b_1|}</math>, как указано выше, образуют последовательные [[подходящие дроби]], а числитель и знаменатель следующей подходящей дроби всегда больше, чем у предыдущей<ref name=SUSH/><ref>{{книга|автор=Хинчин А. Я.|заглавие=Цепные дроби|издание=Изд. 3-е|место=М.|издательство=ГИФМЛ|год=1961|страницы=11—12}}</ref>. Для краткости можно назвать такую пару ''минимальной'', таких пар всегда две.

Пример. Пусть <math>a = 12, b = 42</math>. НОД(12, 42) = 6. Ниже приведены некоторые элементы списка пар коэффициентов Безу, причём минимальные пары выделены красным цветом:
: <math>
\begin{alignat}{3}
&\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{alignat}
</math>

== Применение ==
Соотношение Безу часто используется как [[лемма]] в ходе доказательства других теорем (например, [[основная теорема арифметики|основной теоремы арифметики]]<ref>См., например: {{статья |автор=Жиков В. В. |заглавие=Основная теорема арифметики |издание=[[Соросовский Образовательный Журнал]] |год=2000 |том=6 |номер=3 |страницы=112–117 |ссылка=http://www.pereplet.ru/nauka/Soros/pdf/0003_112.pdf}}</ref>), а также для решения диофантовых уравнений и сравнений по модулю.

=== Решение диофантовых уравнений первой степени ===
Рассмотрим решение в целых числах [[Диофантово уравнение|диофантовых уравнений]] вида
: <math>ax + by = c.</math>
Обозначим <math>d = {}</math>НОД<math>(a, b).</math> Очевидно, уравнение имеет целочисленные решения только в том случае, когда <math>c</math> делится на <math>d</math>. Будем считать это условие выполненным, и одним из приведённых выше алгоритмов найдём коэффициенты Безу <math>x, y</math>:
: <math>ax + by = d.</math>
Тогда решением исходного уравнения будет пара<ref name=SUSH/> <math>c_1 x, c_1 y</math>, где <math>c_1 = c / d</math>.

=== Решение сравнений первой степени ===
Для решения [[Сравнение по модулю|сравнений первой степени]]
: <math>ax \equiv b \pmod m</math>
его достаточно преобразовать к виду<ref name=brill/>
: <math>ax + my = b.</math>
Практически важным частным случаем является нахождение обратного элемента в [[Сравнение по модулю|кольце вычетов]], то есть решение сравнения
: <math>ax \equiv 1 \pmod m.</math>

== Вариации и обобщения ==
Соотношение Безу легко обобщается на случай, когда имеется более двух чисел<ref name=HASSE/>:
{{рамка}}
Пусть <math>a_1</math>, …, <math>a_n</math> — целые числа, не все равные нулю. Тогда существуют такие целые числа <math>x_1</math>, …, <math>x_n</math>, что выполняется соотношение:
: НОД<math>(a_1</math>, …, <math>a_n)</math> = <math>x_1\cdot a_1 + \cdots x_n\cdot a_n</math>
{{конец рамки}}

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

Пример: формулировка для [[кольцо многочленов|кольца многочленов]] (от одной переменной):
{{рамка}}
Пусть <math>\left(P_i\right)_{i\in I}</math> — какое-либо семейство многочленов, и не все они равны нулю. Обозначим <math>\Delta</math> их наибольший общий делитель. Тогда существует такое семейство многочленов <math>\left(A_i\right)_{i\in I}</math>, что выполняется соотношение:
: <math>\Delta = \sum_{i\in I} A_iP_i</math>
{{конец рамки}}

Коэффициенты Безу для двух многочленов от одной переменной могут быть вычислены аналогично изложенному выше для целых чисел (с помощью [[Алгоритм Евклида|расширенного алгоритма Евклида]])<ref>{{книга |автор=Коблиц Н. |заглавие=Курс теории чисел и криптографии|место=М.|издательство=Научное изд-во ТВП |год=2001 |страниц=259 |страницы=19 |isbn=5-94057-103-4 }}</ref>. Общие корни двух многочленов являются корнями также и их наибольшего общего делителя, поэтому из соотношения Безу и [[основная теорема алгебры|основной теоремы алгебры]] вытекает следующий результат:

{{рамка}}
Пусть даны многочлены <math>f(x)</math> и <math>g(x)</math> с коэффициентами в некотором поле. Тогда многочлены <math>a(x)</math> и <math>b(x)</math> такие, что <math>af + bg = 1</math>, существуют тогда и только тогда, когда <math>f(x)</math> и <math>g(x)</math> не имеют общих корней ни в каком алгебраически замкнутом поле (обычно в качестве последнего берётся поле [[Комплексное число|комплексных чисел]]).
{{конец рамки}}

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

== См. также ==
* [[Алгоритм Евклида]]
* [[Диофантово уравнение]]
* [[Наибольший общий делитель]]
* [[Сравнение по модулю#Решение сравнений|Решение сравнений]]
* [[Сравнение по модулю]]

== Примечания ==
{{примечания}}

== Литература ==
* {{книга |автор=[[Виноградов, Иван Матвеевич|Виноградов И. М.]]
  |заглавие=Основы теории чисел |издательство=ГИТТЛ |место=М.-Л. |год=1952 |страниц=180 }}
* {{книга |автор=Калужнин Л. А.|заглавие=Основная теорема арифметики
  |серия=[[Популярные лекции по математике]] |выпуск=47|место=М. |издательство=Наука |год=1969}}
* {{книга |автор=[[Хассе, Хельмут|Хассе Г.]]|заглавие=Лекции по теории чисел |место=М.
  |издательство=Изд. иностранной литературы |год=1953 |страниц=529 |ref=Хассе Г. }}

== Ссылки ==
* [http://wims.unice.fr/wims/wims.cgi?module=tool/arithmetic/bezout.en Онлайн-калькулятор] коэффициентов соотношения Безу.
* [https://math.dartmouth.edu/archive/m25f11/public_html/notes/class4.pdf Bezout’s Identity ]{{ref-en}}.
* [http://public.csusm.edu/aitken_html/m422/Handout1.pdf Bezout’s identity, Euclidean algorithm]{{ref-en}}.

{{Добротная статья|Математика}}

[[Категория:Диофантовы уравнения]]
[[Категория:Теоремы теории чисел]]
[[Категория:Теоремы алгебры|Б]]