Bezout nisbati
Bezout nisbati- butun sonlarning eng katta umumiy boʻluvchisining butun son koeffitsientlari bilan chiziqli birikmasi sifatida tasviri hisoblanadi .
Bezout nisbati Fransuz matematigi 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. 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.
Etyen Bezout o'zining 1766-yil 3-jilddagi "Matematika kurslari" nomli to'rt jildlik asarida teoremani ixtiyoriy sonlar juftligiga ham, ko'phadlarga ham kengaytirish orqali umumlashtirgandir[⇨].
Keltirib chiqarishi
GCD
(
a
,
b
)
=
x
⋅
a
+
y
⋅
b
{\displaystyle (a,b)=x\cdot a+y\cdot b}
|}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
a
{\displaystyle a}
va
b
{\displaystyle b}
), shuningdek, Bezout lemmasi yoki Bezoutning shaxsi. Butun sonlar bo'lganda
x
,
y
{\displaystyle x,y}
Bezout koeffitsientlari deb ataladi.
Natural sonlar bilan cheklangan Bezout munosabatining modifikatsiyasi ham mavjud hisoblanadi:
????, ???? natural sonlar boʻlsin. U holda ????,???? natural sonlar borki,GCD (????,????)=????⋅????−????⋅???? munosabati
Bezout koeffitsientlari
Yechimlari
Agar raqamlar
a
,
b
{\displaystyle a,b}
ko‘paytma va keyin tenglama
a
x
+
b
y
=
1
{\displaystyle ax+by=1}
butun sonli yechimlarga ega bo'ladi. Bu muhim fakt birinchi darajali diofant tenglamalarini yechishni osonlashtiradi.
GCD
(
a
,
b
)
{\displaystyle (a,b)}
sonlarning chiziqli birikmasi sifatida ifodalanishi mumkin bo‘lgan eng kichik natural sondir
a
{\displaystyle a}
va
b
{\displaystyle b}
butun son koeffitsientlari bilan hisoblanadi.
Ko'p sonli chiziqli birikmalar
{
a
x
+
b
y
}
{\displaystyle \{ax+by\}}
GCD uchun ko'paytmalar to'plamlariga to'g'ri keladi:
(
a
,
b
)
{\displaystyle (a,b)}
.
Bezout koeffitsientlari
Raqamlardan kamida bittasi nol bo'lgan holatdan beri
a
,
b
{\displaystyle a,b}
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 tenglamasini yechish usuli bilan hisoblaymiz:
a
x
+
b
y
=
d
,
{\displaystyle ax+by=d,}
Buyerda
d
=
{\displaystyle d=}
GCD
(
a
,
b
)
.
{\displaystyle (a,b).}
Yoki, bu bilan bir xil:
a
d
x
+
b
d
y
=
1.
{\displaystyle {\frac {a}{d}}x+{\frac {b}{d}}y=1.}
Bundan kelib chiqadiki, Bezout koeffitsientlari
x
,
y
{\displaystyle x,y}
noaniq belgilangan - agar ularning ba'zi qiymatlari
x
0
,
y
0
{\displaystyle x_{0},y_{0}}
ma'lum bo'lsa, u holda barcha koeffitsientlar to'plami formula bilan hisoblash mumkin bo'ladi.
{
(
x
0
+
k
b
d
,
y
0
−
k
a
d
)
∣
k
=
0
,
±
1
,
±
2
,
±
3
…
}
.
{\displaystyle \left\{\left(x_{0}+{\frac {kb}{d}},y_{0}-{\frac {ka}{d}}\right)\mid k=0,\pm 1,\pm 2,\pm 3\dots \right\}.}
Quyida ko'rsatiladi[⇨] tengsizliklarni qanoatlantiruvchi Bezout koeffitsientlari mavjud bo'lishi uchun
|
x
|
<
|
b
d
|
{\displaystyle |x|<\left|{\frac {b}{d}}\right|}
Va
|
y
|
<
|
a
d
|
{\displaystyle |y|<\left|{\frac {a}{d}}\right|}
.
Evklid algoritmi yordamida koeffitsientlarni hisoblash
Bezout koeffitsientlarini topish uchun siz GCD ni topish keyin kengaytirilgan Evklid algoritmidan foydalanishingiz va qoldiqlarni a va bning chiziqli birikmalari sifatida ko'rsatishingiz kerak. Algoritmning bosqichlari quyidagi shaklda ham yoziladi:
r
1
=
a
−
b
q
0
,
{\displaystyle r_{1}=a-bq_{0},}
r
2
=
b
−
r
1
q
1
=
b
−
(
a
−
b
q
0
)
q
1
=
b
(
1
+
q
0
q
1
)
−
a
q
1
,
{\displaystyle r_{2}=b-r_{1}q_{1}=b-(a-bq_{0})q_{1}=b(1+q_{0}q_{1})-aq_{1},}
r
3
=
r
1
−
r
2
q
2
=
(
a
−
b
q
0
)
−
(
b
(
1
+
q
0
q
1
)
−
a
q
1
)
q
2
=
a
(
1
+
q
1
q
2
)
−
b
(
q
0
+
q
2
+
q
0
q
1
q
2
)
,
{\displaystyle r_{3}=r_{1}-r_{2}q_{2}=(a-bq_{0})-(b(1+q_{0}q_{1})-aq_{1})q_{2}=a(1+q_{1}q_{2})-b(q_{0}+q_{2}+q_{0}q_{1}q_{2}),}
…
r
n
=
r
n
−
2
−
r
n
−
1
q
n
−
1
=
⋯
=
a
x
+
b
y
.
{\displaystyle r_{n}=r_{n-2}-r_{n-1}q_{n-1}=\dots =ax+by.}
Misol
Quyidagi uchun Bezout munosabatini toping
a
=
991
,
b
=
981.
{\displaystyle a=991,b=981.}
Evklid algoritmining formulalari shaklga ega bo'lsin:
991
=
981
⋅
1
+
10
,
{\displaystyle 991={\boldsymbol {981}}\cdot 1+10,}
981
=
10
⋅
98
+
1
,
{\displaystyle {\boldsymbol {981}}=10\cdot 98+1,}
10
=
1
⋅
10.
{\displaystyle 10=1\cdot 10.}
Shunday qilib, GCD
(
991
,
981
)
=
1
{\displaystyle (991,981)=1}
. Ushbu formulalardan biz quyidagilarni bilib olamizshimiz mumkin:
10
=
991
−
1
⋅
981
,
{\displaystyle 10={\boldsymbol {991}}-1\cdot {\boldsymbol {981}},}
1
=
981
−
10
⋅
98
=
981
−
98
⋅
(
991
−
981
)
=
99
⋅
981
−
98
⋅
991
.
{\displaystyle 1={\boldsymbol {981}}-10\cdot 98={\boldsymbol {981}}-98\cdot ({\boldsymbol {991}}-{\boldsymbol {981}})=99\cdot {\boldsymbol {981}}-98\cdot {\boldsymbol {991}}.}
Natijada, Bezout munosabati quyigagi shaklga ega bo'ladi
1
=
99
⋅
981
−
98
⋅
991
.
{\displaystyle 1=99\cdot {\boldsymbol {981}}-98\cdot {\boldsymbol {991}}.}
Davomli kasrlar yordamida koeffitsientlarni hisoblash:
Tenglamani yechishning muqobil (taqriban ekvivalent) usullaridan biri
a
x
+
b
y
=
d
{\displaystyle ax+by=d}
davomli kasrlarni ishlatadi. Tenglamaning ikkala tomonini GCD ga bo'lamiz:
a
1
x
+
b
1
y
=
1
{\displaystyle a_{1}x+b_{1}y=1}
. Keyin esa biz
|
a
1
|
|
b
1
|
{\displaystyle {\frac {|a_{1}|}{|b_{1}|}}}
davomli kasrga aylantiramiz va konvergentlarni hisoblaymiz
p
k
q
k
{\displaystyle {\frac {p_{k}}{q_{k}}}}
. Oxirgi (
n
{\displaystyle n}
-я) ulardan teng bo'ladi
|
a
1
|
|
b
1
|
{\displaystyle {\frac {|a_{1}|}{|b_{1}|}}}
va oldingi doimgi munosabat bilan bog'liq:
p
n
q
n
−
1
−
q
n
p
n
−
1
=
(
−
1
)
n
−
1
.
{\displaystyle p_{n}q_{n-1}-q_{n}p_{n-1}=(-1)^{n-1}.}
Ushbu formulani almashtiramiz
p
n
=
a
1
;
q
n
=
b
1
{\displaystyle p_{n}=a_{1};q_{n}=b_{1}}
va ikkala tomonni
d
{\displaystyle d}
ga ko'paytirib olamiz
a
q
n
−
1
−
b
p
n
−
1
=
±
d
.
{\displaystyle aq_{n-1}-bp_{n-1}=\pm d.}
Birinchi belgigacha, bu Bezoutning nisbati. shuning uchun oxirgi konvergent
p
n
−
1
q
n
−
1
{\displaystyle {\frac {p_{n-1}}{q_{n-1}}}}
yechimining modullarini beradi:
|
x
|
{\displaystyle |x|}
bu kasrning maxraji bo'ladi va
|
y
|
{\displaystyle |y|}
- surati hisoblanadi. Asl tenglamaga asoslanib, belgilarni topish qoladi
x
,
y
{\displaystyle x,y}
; Buning uchun tenglamalarning oxirgi raqamlarni topish kifoya
|
a
x
|
,
|
b
y
|
{\displaystyle |ax|,|by|}
.
Minimal juftlik koeffitsientlari
Davomli kasrlar nuqtai nazaridan oldingi bobda berilgan algoritmlar, shuningdek Evklidning ekvivalent algoritmlari juftlikni keltirib chiqaradi.
(
x
,
y
)
{\displaystyle (x,y)}
, tengsizliklarni qoniqtiradi:
|
x
|
<
|
b
d
|
;
|
y
|
<
|
a
d
|
.
{\displaystyle |x|<\left|{\frac {b}{d}}\right|;\quad |y|<\left|{\frac {a}{d}}\right|.}
Bu teorema kasrlar ekanligidan kelib chiqadi
|
y
|
|
x
|
{\displaystyle {\frac {|y|}{|x|}}}
Va
|
a
1
|
|
b
1
|
{\displaystyle {\frac {|a_{1}|}{|b_{1}|}}}
, yuqoridagi kabi, ketma-ket yaqinlashuvchilarni hosil qiladi va keyingi yaqinlashuvchining soni va maxraji har doim oldingi dan kattaroq bo'ladi. Qisqartirish uchun biz bunday juftlikni minimal deb atashimiz mumkin, har doim ikkita bunday juftlik mavjud bo'ladi.
Misol. Mayli
a
=
12
,
b
=
42
{\displaystyle a=12,b=42}
. GSD(12, 42) = 6. Quyida Bezout koeffitsientlari juftlari ro'yxatining ba'zi elementlari qiymatlari, minimal juftliklar qizil rang bilan belgilangan:
…
12
×
−
10
+
42
×
3
=
6
12
×
−
3
+
42
×
1
=
6
12
×
4
+
42
×
−
1
=
6
12
×
11
+
42
×
−
3
=
6
12
×
18
+
42
×
−
5
=
6
…
{\displaystyle {\begin{alignedat}{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{alignedat}}}
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 tenglamalarining yechimini butun sonlarda ko'rib chiqamiz
a
x
+
b
y
=
c
.
{\displaystyle ax+by=c.}
Quyidagicha belgilaymiz
d
=
{\displaystyle d={}}
GCD
(
a
,
b
)
.
{\displaystyle (a,b).}
Shubhasiz, tenglama faqat agar butun sonli yechimlarga ega
c
{\displaystyle c}
tomonidan
d
{\displaystyle d}
ga bo'linadi . Biz bu shartni bajarilgan deb hisoblaymiz va yuqoridagi algoritmlardan biri Bezout koeffitsientlarini topgan bo'lamiz.
x
,
y
{\displaystyle x,y}
:
a
x
+
b
y
=
d
.
{\displaystyle ax+by=d.}
Shunda asl tenglamaning yechimi quyidagi juft qiymat bo‘ladi.
c
1
x
,
c
1
y
{\displaystyle c_{1}x,c_{1}y}
, Qayerda
c
1
=
c
/
d
{\displaystyle c_{1}=c/d}
.
Birinchi darajali taqqoslashlarni yechish usuli
Birinchi darajali taqqoslashlarni yechish:
a
x
≡
b
(
mod
m
)
{\displaystyle ax\equiv b{\pmod {m}}}
uni shaklga keltirish kifoya:
a
x
+
m
y
=
b
.
{\displaystyle ax+my=b.}
Amaliy muhim maxsus holat - bu qoldiq halqadagi o'zaro elementni topishdir, ya'ni taqqoslashni hisoblash.
a
x
≡
1
(
mod
m
)
.
{\displaystyle ax\equiv 1{\pmod {m}}.}
Variatsiyalar va umumlashtirishlar
Bezoutning munosabati ikkitadan ko'p bo'lgan holatlarga osongina umumlashtiriladi :
(
a
1
{\displaystyle (a_{1}}
, …,
a
n
)
{\displaystyle a_{n})}
=
x
1
⋅
a
1
+
⋯
x
n
⋅
a
n
{\displaystyle x_{1}\cdot a_{1}+\cdots x_{n}\cdot a_{n}}
(????,????)=????⋅????+????⋅????
Bezout munosabati nafaqat butun sonlar uchun, balki boshqa kommutativ halqalarda ham (masalan, Gauss butun sonlari uchun) ham amal sifatida ishlatish mumkin. Bunday halqalar Bezout halqalari deb ataladi.
Misol: polinomli halqaning formulasi (bitta o'zgaruvchili):
|
x
|
<
|
b
d
|
;
|
y
|
<
|
a
d
|
.
{\displaystyle |x|<\left|{\frac {b}{d}}\right|;\quad |y|<\left|{\frac {a}{d}}\right|.}
Δ
=
∑
i
∈
I
A
i
P
i
{\displaystyle \Delta =\sum _{i\in I}A_{i}P_{i}}
Bitta o'zgaruvchidagi ikkita polinom uchun Bezout koeffitsientlari butun sonlar uchun yuqoridagi kabi hisoblanishi ham mumkin ( kengaytirilgan Evklid algoritmi yordamida ham) bo'ladi. Ikki polinomning umumiy ildizlari ham ularning eng katta umumiy boʻluvchisining ildizlari bo'ladi, shuning uchun Bezout munosabati va 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
Havolalar
Havolalar
uz.wikipedia.org