Algebra va sonlar nazariyasi

a n
f₂( x) = f( x) - xⁿ-^mg (x), ^b0
bu yerda a₁₀ koeffitsient f (x) ko‘phadning bosh koeffitsienti. Ma’lumki,
n2 = deg f,( x) < deg f (x) = n bo‘lib, yuqoridagi mulohazani yana bir bor qo‘llash mumkin. Bu jarayonni davom ettirish natijasida darajalari kamayib boruvchi n > n > n₂ >... sonlariga teng bo‘lgan f (x), f (x), f₂(x),... ko‘phadlarni hosil qilamiz. f(x) ko‘phadning darajasi chekli bo‘lganligi uchun, chekli qadamdan so‘ng shunday f_k(x) ko‘phad topilib, n = deg f_k(x) < degg(x) bo‘ladi. Ya’ni quyidagi tenglik o‘rinli
a_t, _n
f_k (x) = f_k -(x) - x^nk-1-mg (x), ^bo
bu yerda а_{н 0} element f_k__x (x) ning bosh koeffitsientidir. Endi hosil bo‘lgan hamma tengliklarni qo‘shsak,
f (x) - f x^n-m + ⁰⁰ x^n-m +... + ^ x^nk-^I-m 1 g (x) = f_k (x) l^b0 ^bo ^b0 У
hosil bo‘ladi. Bundan

q( x) = ^ x^n-m + ^ x”^1-" +... + x^nt-1^-m b b b0 va r (x) = f_k (x) deb olsak,

f (x) - q( x) g( x) = r (x)
ekanligini hosil qilamiz.
Endi (16.4) tenglikni qanoatlantiruvchi q( x) va r (x) ko‘phadlar yagona ekanligini ko‘rsatamiz. Faraz qilaylik, (16.4) tenglik yana boshqa qandaydir q_x (x), r_x (x) e Щх] ko‘phadlar uchun ham o‘rinli bo‘lsin, ya’ni
f (x) = g(x) ■ q1) + r(1), degr(x) < degg(x) ⁽¹⁶.⁵⁾
bo‘lsin. (16.4) va (16.5) tengliklarning chap tomonlari tengligidan g (x) ■ q( x) + r( x) = g (x) ■ q1 (x) + r (x), g( x) ■ (q(x) - q (x)) = r (1) - r( x) kelib chiqadi. Bu tenglikdan quyidagiga ega bo‘lamiz:
deg(r(x) - r(x)) = deg (g (x) • (q(x) - q(x)) ).
Lekin deg(r (x) - r(x)) < degg(x) bo‘lganligi uchun q( x) = q (x) bo‘ladi, bundan r (x) = r( x) tenglik o‘rinli ekanligi kelib chiqadi. □
Misol 16.2. f (x) = 3x³ - 2x² + x + 4 ko‘phadni g(x) = x² + 3x +1 ko‘phadga qoldiqli bo‘lish quyidagicha amalga oshiriladi:
3x³ - 2x² + x + 4 x² + 3x +1 3x³ + 9 x² + 3x 3x -11 - 11x² - 2 x + 4 -11x² - 33x -11 31x +15
Bundan q(x) = 3x -11 va r( x) = 31x +15 ekanligi kelib chiqadi. Demak,
f (x) = g (x) ■ (3x -11) + (31x + 15) tenglikni hosil qilamiz.


101

17. 
    - §. Ko‘phadlar uchun Yevklid algoritmi
    

Bizga f (x) va g (x) ko‘phadlar berilgan bo‘lsin.

1. 
   ta’rif. Agar px) ko‘phad uchun p(x) | f (x) va p(x) | g(x) o‘rinli bo‘lsa, u holda (p(x) ko‘phad f (x) va g(x) ko‘phadlarning umumiy bo‘luvchisi deyiladi.
   

Ma’lumki, agar p(x) ko‘phad f (x) va g(x) ko‘phadlarning umumiy bo‘luvchisi bo‘lsa, cp(x) ko‘phad ham bu ko‘phadlarning umumiy bo‘luvchisi bo‘ladi. Bundan tashqari, p(x) ko‘phadning bo‘luvchilari ham f (x) va g (x) ko‘phadlarning umumiy bo‘luvchilari bo‘ladi.

2. 
   ta’rif. d (x) ko‘phad f (x) va g (x) ko‘phadlarning umumiy bo‘luvchisi bo‘lib, uning o‘zi ham f(x) va g(x) ko‘phadlarning istalgan boshqa bir p(x) umumiy bo‘luvchilariga bo‘linsa, d(x) ko‘phad f (x) va g(x) ko‘phadlarning eng katta umumiy bo‘luvchisi deyiladi va EKUB(f (x), g(x)) kabi belgilanadi.
   

Ta’kidlash joizki, f (x) va g(x) ko‘phadlarning eng katta umumiy bo‘luvchisi darajasi qolgan umumiy bo‘luvchilar darajalaridan kichik bo‘lmaydi.
Ushbu mavzuda ko‘phadlarning eng katta umumiy bo‘luvchisini topish usuli bo‘lgan Yevklid algoritmini keltiramiz.
Umumiylikka ziyon yetkazmagan holda deg f (x) > deg g(x) deb olamiz.
f (x) ni g(x) ga bo‘lib, q (x) bo‘linma va r (x) qoldiqni hosil qilamiz
f (x) = g( x) ■ q (x) + r (x).
Ma’lumki, degg(x) > degr (x), so‘ngra g(x) ni r (x) ga bo‘lib, q₂ (x) bo‘linma va r₂ (x) qoldiqni olamiz:
g (x) = r (x) ■ q2 (x) + r2 (x).
So‘ngra r (x) ni r₂ (x) ga bo‘lib, bu jarayonni shu tarzda davom ettiramiz. Qoldiqlarning darajalari

deg g (x) > deg r (x) > deg r₂ (2) >... tartibda pasayib borganligi va degg(x) chekli bo‘lganligi uchun tengsizliklar zanjiri ma’lum joyga kelib tugaydi, ya’ni deg г_и+1( x) = 0. Demak, biz qiyidagi tengliklarga ega bo‘lamiz: f (x) = g (x) • q( x) + r( x), g (x) = r( x) • 42 (x) + r₂( x), r( x) = r₂( x) • 4з( x) + r,( x), (17.1)

^rn-3^(x) = ^rn-2^(x) • 4n-1 ^(x) + ^Гп-1 ^(X),
rn-2^{( x)} = ^rn-i^{( x)} • q„^(x) + ^r„^(x)
Гп-1^(x) = ^Гп ^(x) • 4n+1^(x).
Endi bu tengliklarning oxirgisidan yuqoriga qarab harakat qilsak,
^rn ^(x) I ^rn-1 ^(x) ^ ^rn ^(x) I ^rn-2 ^(x) ^ ^rn ^(x) I ^rn-3 ^(x) ^
^... ^ г„(x) I r (x) ^ г„(x) I g(x) ^ г„(x) I f (x) hosil bo‘ladi.
Ravshanki, f (x) va g(x) ko‘phadlar uchun tuzilgan Yevklid algoritmidagi ^rn (x) qoldiq bu ko‘phadlarning umumiy bo‘luvchisi bo‘ladi. Demak, Yevklid algoritmi f(x) va g(x) ko‘phadlarni umumiy bo‘luvchilarini topish usulini berar ekan.

3. 
   teorema. f (x) va g (x) ko‘phadlar uchun tuzilgan Yevklid algoritmidagi oxirgi noldan farqli qoldiq ^rn (x) ularning eng katta umumiy bo‘luvchisiga teng, ya’ni EKUB( f (x), g( x)) = r„ (x).
   

Isbot. Yuqorida ^rn (x) qoldiq f (x) va g(x) ko‘phadlarning umumiy bo‘luvchisi ekanligini aytib o‘tdik. Faraz qilaylik, d(x) ko‘phad f (x) va g (x) laming boshqa bir umumiy bo‘luvchisi bo‘lsin. U holda Yevklid algoritmidan ko‘rish mumkinki, d(x)| r (x) o‘rinli bo‘ladi, shuningdek, d(x)| r (x) munosabat ham o‘rinli ekanligini tekshirish qiyin emas. Bu jarayonni davom attirish natijasida d(x) | r_n(x) ekanligini hosil qilamiz. I


103

3. 
   teoremadan shuni xulosa qilish mumkinki, berilgan ko‘phadlarning eng katta umumiy bo‘luvchisini Yevklid algoritmi yordamida topish mumkin. Shuningdek, agar d (x) berilgan ko‘phadlarning EKUBi bo‘lsa, u holda ixtiyoriy c nolinchi darajali ko‘phad uchun cd (x) ko‘phad ham berilgan ko‘phadlarning EKUBi bo‘ladi.
   

Misol 17.1. Yevklid algoritmi yordamida f (x) = x³ + x² - x -1 va g(x) = x³ -1 ko‘phadlarning EKUBini topaylik.
f^(x) = g^(x) ■¹ + ^{(x2 - x),} g(x) = (x² - x)(x +1) + (x -1),
(x² - x) = (x -1) ■ x.
Demak, EKUB(f (x), g( x)) = x -1.

3. 
   ta’rif. Agar f (x) va g(x) ko‘phadlar nolinchi darajali ko‘phadlardan boshqa umumiy bo‘luvchilarga ega bo‘lmasa, ushbu ko‘phadlar o‘zaro tub ko‘phadlar deyiladi.
   

Bundan keyin berilgan ko‘phadlarning EKUBining bosh koeffitsientini hamma vaqt 1 ga teng deb olamiz va shunga asosan o‘zaro tub ko‘phadlarning EKUBi 1 ga teng bo‘ladi. O‘zaro tub ko‘phadlar (f (x), g (x)) = 1 kabi yoziladi.
Endi Yevklid algoritmidan foydalanib, quyidagi teoremani isbot qilamiz.

3. 
   teorema. Ixtiyoriy f(x) va g(x) ko‘phadlar uchun deg u(x) < deg g(x) va deg v(x) < deg f (x) shartni qanoatlantiruvchi shunday u( x), v( x) ko‘phadlar topiladiki,
   

f (x) ■ u(x) + g (x) ■ v(x) = EKUB(f (x), g (x)) (17.2)
tenglik o‘rinli bo‘ladi.
Isbot. Teoremani isbotlash uchun f (x) va g(x) ko‘phadlarga Yevklid algoritmini qo‘llaymiz. Yevklid algoritmidagi oxiridan bitta oldingi tengligini qaraymiz:
^rn-2 ^(x) = ^rn-1 1 ■ 1n ^(x) + ^rn ^(x).

Bundan

^rn ^(x) = ^rn-2 ^{(x) - r}n-1 ⁽1 • in ^(x)
tenglik hosil bo‘ladi. Bu tenglikda г„ (x) = EKUB(f (x), g (x))
ekanligini hisobga olib, щ (x) = l, — (x) = -q„ (x) deb olsak,