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

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

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

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

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

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

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

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

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

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

Вiдповiдно до алгоритму Евклiда дiлення з остачею ${\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}$ — дiльник ${\displaystyle a}$. Аналогiчно, ${\displaystyle d}$ також є дiльником ${\displaystyle b}$, і ${\displaystyle d}$ — спiльний дiльник ${\displaystyle a}$ та ${\displaystyle b}$.

Нехай ${\displaystyle c}$ — будь-який спiльний дiльник ${\displaystyle a}$ та ${\displaystyle b}$; тобто iснують такi ${\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}$.

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

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

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