Рівняння Безу

В елементарній теорії чисел, тотожність (рівняння) Безу (також використовують назву лема Безу) це наступна теорема:

Тотожність Безу. Нехай ${\displaystyle a}$ i ${\displaystyle b}$ цілі числа з найбільшим спільним дільником ${\displaystyle d}$. Тоді існують цілі числа ${\displaystyle x}$ і ${\displaystyle y}$ такі, що ${\displaystyle ax+by=d}$. Більш точніше, цілі числа вигляду ${\displaystyle ax+by}$ є дільниками ${\displaystyle d}$.

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

Як приклад, найбільшим спільним дільником 15 i 69 є 3, i можна записати ${\displaystyle 15\cdot (-9)+69\cdot 2=3}$.

Багато інших теорем в елементарній теорії чисел, таких як Лема Евкліда або китайська теорема про остачі, є наслідками рівняння Безу.

Кільце Безу — це область цілісності, в якій виконується рівняння Безу. Зокрема, рівняння Безу виконується в області головних ідеалів. Таким чином, кожна теорема, яка випливає з рівняння Безу, є справедливою у всіх цих областях.

Структура розв’язку

Якщо ${\displaystyle a}$ i ${\displaystyle b}$ не є одночасно нулями, i одна пара коефіцієнтів Безу ${\displaystyle (x,y)}$ була знайдена (наприклад, за допомогою розширеного алгоритму Евкліда), то усі пари можна представити у вигляді

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

де ${\displaystyle k}$ — довільне ціле число, ${\displaystyle d}$ — найбільший спільний дільник чисел ${\displaystyle a}$ та ${\displaystyle b}$, i дроби спрощено до цілих чисел.

Якщо обидва ${\displaystyle a}$ i ${\displaystyle b}$ ненульові, тоді рівно дві з цих пар коефіцієнтів Безу задовольняють умови

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

а рівність може мати місце лише в тому випадку, якщо одне з ${\displaystyle a}$ та ${\displaystyle b}$ ділить інше. Це випливає з властивості ділення з остачею: нехай задано два ненульових цілих числа ${\displaystyle c}$ i ${\displaystyle d}$, якщо ${\displaystyle d}$ не ділить ${\displaystyle c}$, то є рівно одна пара ${\displaystyle (q,r)}$ така, що ${\displaystyle c=dq+r}$ та ${\displaystyle 0<r<|d|}$, та іще одна пара така, що ${\displaystyle c=dq+r}$ та ${\displaystyle |d|<r<0}$.

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

Розширений алгоритм Евкліда завжди дає одну з цих двох мінімальних пар.

Приклад

Нехай ${\displaystyle a=12}$ i ${\displaystyle b=42}$, тоді ${\displaystyle {\text{НСД}}(12,42)=6}$ i маємо наступні рівняння Безу, де червоним позначено коефіцієнти Безу для мінімальних пар i синім для інших:

${\displaystyle {\begin{aligned}\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{aligned}}}$

Якщо ${\displaystyle (x,y)=(18,-5)}$ — початкова пара коефіцієнтів Безу, тоді ${\displaystyle {\frac {18}{42/6}}\in [2,3]}$ визначає мінімальну пару для ${\displaystyle k=2}$ та ${\displaystyle k=3}$ тобто ${\displaystyle (18-2\cdot 7,-5+2\cdot 2)=(4,-1)}$ i ${\displaystyle (18-3\cdot 7,-5+3\cdot 2)=(-3,1).}$

Доведення

Нехай задано будь-які ненульові цілі числа ${\displaystyle a}$ та ${\displaystyle b}$ i нехай ${\displaystyle S=\{ax+by\mid x,y\in \mathbb {Z} {\text{ і }}ax+by>0\}}$. Множина ${\displaystyle S}$ не є порожньою, оскільки вона включає або ${\displaystyle a}$, або ${\displaystyle -a}$ (з ${\displaystyle x=\pm 1}$ та ${\displaystyle y=0}$)Оскільки ${\displaystyle S}$ — непорожня множина натуральних чисел, то вона має мінімальний елемент ${\displaystyle d=as+bt}$ принципом цілковитого впорядкування^[en]. Щоб довести, що ${\displaystyle d}$ — найбільший спільний дільник ${\displaystyle a}$ та ${\displaystyle b}$, треба довести, що ${\displaystyle d}$ — спільний дільник ${\displaystyle b}$ та ${\displaystyle b}$, i що для будь-якого іншого спільного дільника ${\displaystyle c}$ виконується нерівність ${\displaystyle c\leq d}$.

Відповідно до алгоритму Евкліда ділення з остачею ${\displaystyle a}$ на ${\displaystyle d}$ отримуємо, що

${\displaystyle a=dq+r\quad {\text{з}}\quad 0\leq r<d.}$

Остача ${\displaystyle r}$ належить ${\displaystyle S\cup \{0\}}$, оскільки

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

Таким чином, ${\displaystyle r}$ має вигляд ${\displaystyle ax+by}$, i отже ${\displaystyle r\in S\cup \{0\}}$. Але ${\displaystyle 0\leq r<d}$ і ${\displaystyle d}$ — найменше натуральне число в ${\displaystyle S}$: отже, остача ${\displaystyle r}$ не може належати ${\displaystyle s}$, тому обов’язково ${\displaystyle r=0}$. Це означає, що ${\displaystyle d}$ — дільник ${\displaystyle a}$. Аналогічно, ${\displaystyle d}$ також є дільником ${\displaystyle b}$, і ${\displaystyle d}$ — спільний дільник ${\displaystyle a}$ та ${\displaystyle b}$.

Нехай ${\displaystyle c}$ — будь-який спільний дільник ${\displaystyle a}$ та ${\displaystyle b}$; тобто існують такі ${\displaystyle u}$ та ${\displaystyle v}$, що ${\displaystyle a=cu}$ і ${\displaystyle b=cv}$. Таким чином,

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

Тобто ${\displaystyle c}$ — дільник ${\displaystyle d}$, а отже, ${\displaystyle c\leq d}$.

Узагальнення

Для трьох або більше цілих чисел

Тотожність Безу можна узагальнити на випадок більш ніж двох цілих чисел: якщо

${\displaystyle {\text{НСД}}(a_{1},a_{2},\dots ,a_{n})=d,}$

тоді є цілі числа ${\displaystyle x_{1},x_{2},\dots ,x_{n}}$ такі, що

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

має наступні властивості:

• ${\displaystyle d}$ — найменше натуральне число такого вигляду,
• будь-яке число такого вигляду кратне ${\displaystyle d}$.

Для многочленів

Тотожність Безу працює i у випадку многочленів однієї змінної над деяким полем точно так само, як i для цілих чисел. Зокрема, коефіцієнти Безу та найбільший спільний дільник можуть бути обчислені за допомогою розширеного алгоритму Евкліда.

Оскільки спільні корені двох многочленів є коренями їх найбільшого спільного дільника, то тотожність Безу i основна теорема алгебри дають наступний результат:

Для многочленів ${\displaystyle f}$ i ${\displaystyle g}$ однієї змінної i з коефіцієнтами над деяким полем існують поліноми ${\displaystyle a}$ i b такі, що ${\displaystyle af+bg=1}$, тоді i лише тоді, якщо ${\displaystyle f}$ i ${\displaystyle g}$ не мають спільного кореня в будь-якому алгебраїчно замкненому полі (зазвичай це поле комплексних чисел).

Узагальнення цього результату на випадок довільної кількості поліномів та невизначених рівнянь є Теорема Гільберта про нулі.

Для області головних ідеалів

Як зазначено у вступі, тотожність Безу працює не тільки в кільці цілих чисел, але i в будь-якій іншій області головних ідеалів.Тобто, якщо ${\displaystyle R}$ — область головних ідеалів, ${\displaystyle a}$ і ${\displaystyle b}$ — елементи ${\displaystyle R}$, i ${\displaystyle d}$ є найбільшим спільним дільником ${\displaystyle a}$ і ${\displaystyle b}$, тоді в ${\displaystyle R}$ є елементи ${\displaystyle x}$ і ${\displaystyle y}$ такі, що ${\displaystyle ax+by=d}$. Причина у тому, що ідеал ${\displaystyle Ra+Rb}$ є головним i дорівнює ${\displaystyle Rd}$.

Область цілісності в якій виконується тотожність Безу називається кільцем Безу.

Історія

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

Див. також

• Теорема AF + BG^[en]
• Основна теорема арифметики
• Лема Евкліда

Примітки

1. Bézout, É. (1779). Théorie générale des équations algébriques. Paris, France: Ph.-D. Pierres.
2. Tignol, Jean-Pierre (2001). Galois' Theory of Algebraic Equations. Singapore: World Scientific. ISBN 981-02-4541-6.
3. Claude Gaspard Bachet (sieur de Méziriac) (1624). Problèmes plaisants & délectables qui se font par les nombres (вид. 2nd). Lyons, France: Pierre Rigaud & Associates. с. 18—33. На цих сторінках Баше доводить (без рівнянь) "Proposition 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." (Для заданих двох взаємнопростих чисел знайти найменше кратне кожного з них таке, що одне перевищує інше на одиницю.) Ця задача (а саме, ${\displaystyle ax-by=1}$) є окремим випадком рівняння Безу i була використана Баше для розв’язання проблем, що з’являються на сторінках 199 i далі.
4. Див. також: Maarten Bullynck (February 2009). Modular arithmetic before C.F. Gauss: Systematizations and discussions on remainder problems in 18th-century Germany (PDF). Historia Mathematica. 36 (1): 48—72. doi:10.1016/j.hm.2008.08.009.

Зовніші лінки

• Онлайн-калькулятор для рівняння Безу.
• Weisstein, Eric W. Bézout's Identity(англ.) на сайті Wolfram MathWorld.