Bezout nisbati sahifasining manbasini koʻrish

'''Bezout nisbati-''' butun sonlarning eng katta umumiy boʻluvchisining butun son koeffitsientlari bilan chiziqli birikmasi sifatida tasviri hisoblanadi{{Sfn|Хассе Г.|1953}} .

'''Bezout nisbati''' Fransuz matematigi [[Bezu, Etyen|Etyen Bezout]] sharafiga nomlangan.

== Tarixi ==
Birinchi marta bu fakt 1624-yilda fransuz matematigi Klod Gaspard Bachet de Meziriac tomonidan nisbatan tub sonlar ishi uchun e'lon qilingan<ref>{{Kitob manbasi/Ruscha|title=История математики}}</ref>. Bashe formulasi quyidagicha: “''Ikki [oʻzaro] tub son berilgan boʻlsa, har birining boshqasiga bir karrali boʻlgan eng kichik karralini topish''” . Muammoni hal qilish uchun Basche Evklid algoritmidan ham foydalangan.

[[Bezu, Etyen|Etyen Bezout]] o'zining 1766-yil 3-jilddagi ''"Matematika kurslari" nomli to'rt jildlik asarida'' teoremani ixtiyoriy sonlar juftligiga ham, [[Koʻphad|ko'phadlarga]] ham kengaytirish orqali umumlashtirgandir{{Oʻtishga|Вариации и обобщения}}.

== Keltirib chiqarishi ==
: GCD<math>(a, b) = x \cdot a + y \cdot b</math>
|}Mayli 𝑎,𝑏- kamida bittasi nolga teng bo'lmagan butun sonlardir. Keyin bunday butun sonlar mavjud 𝑥,𝑦, bu munosabat GCD

(𝑎,𝑏)=𝑥⋅𝑎+𝑦⋅𝑏

Ushbu bayonot '''Bezout munosabati''' deb ataladi (son qiymatlar uchun <math>a</math> va <math>b</math>), shuningdek, ''Bezout lemmasi'' yoki ''Bezoutning shaxsi''<ref>{{Kitob manbasi/Ruscha|автор=Jones, G. A., Jones, J. M.|часть=§1.2. Bezout's Identity|заглавие=Elementary Number Theory|место=Berlin|издательство=Springer-Verlag|год=1998|pages=7—11}}</ref>. Butun sonlar bo'lganda <math>x, y</math> '''Bezout koeffitsientlari''' deb ataladi.

[[Natural son|Natural sonlar bilan]] cheklangan Bezout munosabatining modifikatsiyasi ham mavjud hisoblanadi<ref>{{Kitob manbasi/Ruscha|автор=Дэвенпорт Г.|заглавие=Высшая арифметика. Введение в теорию чисел|место=М.|издательство=Наука|год=1965}}</ref>:

𝑎, 𝑏 natural sonlar boʻlsin. U holda 𝑥,𝑦 natural sonlar borki,GCD (𝑎,𝑏)=𝑥⋅𝑎−𝑦⋅𝑏 munosabati

== Bezout koeffitsientlari ==

* GCD <math>(12, 30) = 6.</math> Bezout munosabatlari quyidagi shaklarga ega:
*: <math>6=3 \cdot 12 + (-1) \cdot 30</math>
** GCD parchalanishining boshqa variantlari hammavjud, masalan: <math>6=(-2) \cdot 12 + 1 \cdot 30.</math>

== Yechimlari ==
Agar raqamlar <math>a, b</math> ko‘paytma va keyin tenglama

: <math>ax + by = 1</math>

butun sonli yechimlarga ega{{Sfn|Хассе Г.|1953}} bo'ladi. Bu muhim fakt birinchi darajali [[Diofant tenglamalari|diofant tenglamalarini]] yechishni osonlashtiradi.

GCD <math>(a, b)</math> sonlarning chiziqli birikmasi sifatida ifodalanishi mumkin bo‘lgan eng kichik natural sondir <math>a</math> va <math>b</math> butun son koeffitsientlari bilan hisoblanadi<ref>{{Kitob manbasi/Ruscha|автор=Фаддеев Д. К.|заглавие=Лекции по алгебре. Учебное пособие для вузов|издательство=Наука|год=1984}}</ref>.

Ko'p sonli chiziqli birikmalar <math>\{ax + by\}</math> GCD uchun [[Boʻlinishlik|ko'paytmalar]] to'plamlariga to'g'ri keladi: <math>(a,b)</math><ref name="brill">{{Veb manbasi|url=https://brilliant.org/wiki/bezouts-identity/|sarlavha=Bezout's identity|qaralgan sana=2014-12-25|arxivsana=2014-12-25|arxivurl=https://web.archive.org/web/20141225200517/https://brilliant.org/wiki/bezouts-identity/}}</ref>.

== Bezout koeffitsientlari ==
Raqamlardan kamida bittasi nol bo'lgan holatdan beri <math>a,b</math> nolga tengligi ahamiyatsiz, bu bo'limning qolgan qismi bu raqamlarning ikkalasi ham nolga teng emas deb hisoblanadi.

=== Noaniqlik ===
Bezout koeffitsientlarini topish ikkita noma'lumli birinchi tartibli [[Diofant tenglamalari|diofant tenglamasini]] yechish usuli bilan hisoblaymiz:

: <math>a x + b y = d, </math> Buyerda <math>d=</math> GCD<math>(a, b).</math>

Yoki, bu bilan bir xil:

: <math>\frac{a}{d} x + \frac{b}{d} y = 1.</math>

Bundan kelib chiqadiki, Bezout koeffitsientlari <math>x, y</math> noaniq belgilangan - agar ularning ba'zi qiymatlari <math>x_0, y_0</math> ma'lum bo'lsa, u holda barcha koeffitsientlar to'plami<ref>{{Kitob manbasi/Ruscha|title=Решение уравнений в целых числах|date=1983}}</ref> formula bilan hisoblash mumkin bo'ladi.

: <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>

Quyida ko'rsatiladi{{Oʻtishga|Минимальные пары коэффициентов}} tengsizliklarni qanoatlantiruvchi Bezout koeffitsientlari mavjud bo'lishi uchun <math>|x| < \left|\frac{b}{d}\right|</math> Va <math>|y| < \left|\frac{a}{d}\right|</math> .

=== Evklid algoritmi yordamida koeffitsientlarni hisoblash ===
Bezout koeffitsientlarini topish uchun siz GCD ni topish keyin kengaytirilgan Evklid algoritmidan foydalanishingiz va qoldiqlarni ''a'' va ''b''<ref>{{Kitob manbasi/Ruscha|title=Элементы теории чисел|date=1923}}</ref>ning chiziqli birikmalari sifatida ko'rsatishingiz kerak. Algoritmning bosqichlari quyidagi shaklda ham yoziladi:

: <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>

; Misol

Quyidagi uchun Bezout munosabatini toping <math>a = 991, b = 981.</math> Evklid algoritmining formulalari shaklga ega bo'lsin:

: <math>991 = \boldsymbol{981} \cdot 1 + 10,</math>
: <math>\boldsymbol{981} = 10 \cdot 98 + 1,</math>
: <math>10 = 1 \cdot 10.</math>

Shunday qilib, GCD <math>(991, 981) = 1</math> . Ushbu formulalardan biz quyidagilarni bilib  olamizshimiz mumkin:

: <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>

Natijada, Bezout munosabati quyigagi shaklga ega bo'ladi

: <math>1 = 99 \cdot \boldsymbol{981} - 98 \cdot \boldsymbol{991}.</math>

=== Davomli kasrlar yordamida koeffitsientlarni hisoblash: ===
Tenglamani yechishning muqobil (taqriban ekvivalent) usullaridan biri <math>a x + b y = d </math> davomli kasrlarni ishlatadi. Tenglamaning ikkala tomonini GCD ga bo'lamiz: <math>a_1 x + b_1 y = 1</math> . Keyin esa biz <math>\frac{|a_1|}{|b_1|}</math> davomli kasrga aylantiramiz va konvergentlarni hisoblaymiz <math>\frac{p_k}{q_k}</math> . Oxirgi {{Nobr|(<math>n</math>-я)}} ulardan teng bo'ladi <math>\frac{|a_1|}{|b_1|}</math> va oldingi doimgi munosabat bilan bog'liq:

: <math>p_n q_{n-1} - q_n p_{n-1} = (-1)^{n-1}.</math>

Ushbu formulani almashtiramiz  <math>p_n = a_1; q_n = b_1</math> va ikkala tomonni  <math>d</math> ga ko'paytirib olamiz

: <math>a q_{n-1} - b p_{n-1} = \pm d.</math>

Birinchi belgigacha, bu Bezoutning nisbati. shuning uchun oxirgi konvergent <math>\frac{p_{n-1}}{q_{n-1}}</math> yechimining modullarini beradi: <math>|x|</math> bu kasrning maxraji bo'ladi va <math>|y|</math> - surati hisoblanadi. Asl tenglamaga asoslanib, belgilarni topish qoladi <math>x, y</math> ; Buning uchun tenglamalarning oxirgi raqamlarni topish kifoya <math>|ax|, |by|</math> .

=== Minimal juftlik koeffitsientlari ===
Davomli kasrlar nuqtai nazaridan oldingi bobda berilgan algoritmlar, shuningdek Evklidning ekvivalent algoritmlari juftlikni keltirib chiqaradi. <math>(x,y)</math>, tengsizliklarni qoniqtiradi:

: <math>|x| < \left|\frac{b}{d}\right|; \quad |y| < \left|\frac{a}{d}\right|.</math>

Bu teorema kasrlar ekanligidan kelib chiqadi <math>\frac{|y|}{|x|}</math> Va <math>\frac{|a_1|}{|b_1|}</math>, yuqoridagi kabi, ketma-ket yaqinlashuvchilarni hosil qiladi va keyingi yaqinlashuvchining soni va maxraji har doim oldingi <ref name="SUSH">{{Kitob manbasi/Ruscha}}</ref><ref>{{Kitob manbasi/Ruscha|date=1961}}</ref> dan kattaroq bo'ladi. Qisqartirish uchun biz bunday juftlikni ''minimal'' deb atashimiz mumkin, har doim ikkita bunday juftlik mavjud bo'ladi.

Misol. Mayli <math>a = 12, b = 42</math> . GSD(12, 42) = 6. Quyida Bezout koeffitsientlari juftlari ro'yxatining ba'zi elementlari qiymatlari, minimal juftliklar qizil rang bilan belgilangan:

: <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>

== Eslatma ==
Bezout munosabati koʻpincha boshqa teoremalarni isbotlashda (masalan, arifmetikaning asosiy teoremasi ), shuningdek, diofant tenglamalari va modullarni taqqoslashda [[lemma]] sifatida juda ko'p ishlatiladi.

=== Birinchi darajali diofant tenglamalarini yechishda qo'llanishi ===
Quyidagi ko'rinishdagi [[Diofant tenglamalari|Diofant tenglamalarining]] yechimini butun sonlarda ko'rib chiqamiz

: <math>ax + by = c.</math>

Quyidagicha belgilaymiz <math>d = {}</math> GCD <math>(a, b).</math> Shubhasiz, tenglama faqat agar butun sonli yechimlarga ega <math>c</math> tomonidan <math>d</math> ga bo'linadi . Biz bu shartni bajarilgan deb hisoblaymiz va yuqoridagi algoritmlardan biri Bezout koeffitsientlarini topgan bo'lamiz. <math>x, y</math> :

: <math>ax + by = d.</math>

Shunda asl tenglamaning yechimi<ref name="SUSH">{{Kitob manbasi/Ruscha}}</ref> quyidagi juft qiymat bo‘ladi. <math>c_1 x, c_1 y</math>, Qayerda <math>c_1 = c / d</math> .

=== Birinchi darajali taqqoslashlarni yechish usuli ===
Birinchi darajali taqqoslashlarni yechish:

: <math>ax \equiv b \pmod m</math>

uni shaklga keltirish kifoya<ref name="brill">{{Veb manbasi|url=https://brilliant.org/wiki/bezouts-identity/|sarlavha=Bezout's identity|qaralgan sana=2014-12-25|arxivsana=2014-12-25|arxivurl=https://web.archive.org/web/20141225200517/https://brilliant.org/wiki/bezouts-identity/}}</ref>:

: <math>ax + my = b.</math>

Amaliy muhim maxsus holat - bu qoldiq halqadagi o'zaro elementni topishdir, ya'ni taqqoslashni hisoblash.

: <math>ax \equiv 1 \pmod m.</math>

== Variatsiyalar va umumlashtirishlar ==
Bezoutning munosabati ikkitadan ko'p bo'lgan holatlarga osongina umumlashtiriladi  :

<math>(a_1</math>, …, <math>a_n)</math> = <math>x_1\cdot a_1 + \cdots x_n\cdot a_n</math>

(𝑎,𝑏)=𝑥⋅𝑎+𝑦⋅𝑏
Bezout munosabati nafaqat butun sonlar uchun, balki boshqa kommutativ halqalarda ham (masalan, Gauss butun sonlari uchun) ham amal sifatida ishlatish mumkin. Bunday halqalar  [[Bezu halqasi|Bezout halqalari]] deb ataladi.

Misol: polinomli halqaning formulasi (bitta o'zgaruvchili):<math>|x| < \left|\frac{b}{d}\right|; \quad |y| < \left|\frac{a}{d}\right|.</math>
: <math>\Delta = \sum_{i\in I} A_iP_i</math>
Bitta o'zgaruvchidagi ikkita polinom uchun Bezout koeffitsientlari butun sonlar uchun yuqoridagi kabi hisoblanishi ham  mumkin ( kengaytirilgan Evklid algoritmi yordamida ham)<ref>{{Kitob manbasi/Ruscha|title=Курс теории чисел и криптографии}}</ref> bo'ladi. Ikki polinomning umumiy ildizlari ham ularning eng katta umumiy boʻluvchisining ildizlari bo'ladi, shuning uchun Bezout munosabati va [[Algebraning asosiy teoremasi|algebraning asosiy teoremasidan]] quyidagi natija kelib chiqadi:

Polinomlar berilsin 𝑓(𝑥) Va 𝑔(𝑥) ba'zi sohalarda koeffitsientlar bilan. Keyin polinomlar 𝑎(𝑥) Va 𝑏(𝑥) shu kabi 𝑎𝑓+𝑏𝑔=1, agar va faqat agar mavjud bo'lsa𝑓(𝑥) Va 𝑔(𝑥) har qanday algebraik yopiq sohada umumiy ildizlarga ega emas (odatda murakkab sonlar maydoni oxirgisi sifatida qabul qilinadi).

Bu natijaning har qanday ko'phadlar va noma'lumlarning umumiy soniga umumlashtirilishi Gilbertning nol teoremasi hisoblanadi .

== Shuningdek ==

* Evklid algoritmi
* [[Diofant tenglamalari|Diofant tenglamasi]]
* Eng katta umumiy boʻluvchi
* Taqqoslash qarori
* Modul taqqoslash

== Havolalar ==
{{Manbalar}}

*

== Havolalar ==

* Bezout nisbati [http://wims.unice.fr/wims/wims.cgi?module=tool/arithmetic/bezout.en kalkulyatori onlayn] .
* [https://math.dartmouth.edu/archive/m25f11/public_html/notes/class4.pdf Bezoutning shaxsi]{{Ref-en}} <small class="ref-info" style="cursor:help;" title="на английском языке">)</small> .
* [http://public.csusm.edu/aitken_html/m422/Handout1.pdf Bezout identifikatori, Evklid algoritmi]{{Ref-en}} <small class="ref-info" style="cursor:help;" title="на английском языке">)</small> .
[[Turkum:Algebra]]
[[Turkum:Geometriya]]