Олон гишүүнт дээрх Эвклидийн алгоритм

Олон гишүүнт, олон гишүүнт дээрх Эвклидийн алгоритм

Олон гишүүнт, Эвклидийн алгоритм гэж юу вэ?

F- дурын талбар “$x$” ямар нэг үл мэдэгдэгч байг. $x_{0},x_{1},x_{2},x_{3},...$ хэлбэрийн х үсэг бичигдсэн байг. Үүнд х0 үгийг Ф талбарын нэг гэж тооцно. Дээрх үгнүүдийг Ф талбарын элементүүдээр үржүүлж хооронд нь нэмсэн, формаль илэрхийллийг Ф талбар дээрх х үл мэдэгдэгчтэй олон гишүүнт гэнэ. Тийнхүү олон гишүүнтийг f(x) гэж тэмдэглэвэл тодорхойлолт ёсоор:

f(x)=a0xn+a1xn-1+……+an-1x+an (1)

хэлбэртэй байна. a0,а1,….., аn(∈Ф) элементийг олон гишүүнтийн коэффициент гэж нэрлэнэ.

(1) бичиглэлд байгаа тэгээс ялгаатай коэффициенттэй х-ийн зэргийн хамгийн их зэрэг илтгэгчийг олон гишүүнтийн зэрэг, түүний өмнөх коэффициентийг ахмад гишүүний коэффициент гэж нэрлэнэ. Тухайлбал: а0≠0 үед f(x)-ийн зэрэг нь n байна. Үүнийг degf(x)=n гэж товчлон тэмдэглэдэг.

Эвклидийн алгоритм гэдэг нь ерөнхийдөө 2 натурал тооны эсвэл олон гишүүнтийн хамгийн их ерөнхий хуваагчийг олох хялбар аргуудын нэг юм. 2 олон гишүүнт a, b (a ≧ b)-гийн хувьд a-г b-д хуваахад гарах үлдэгдлийг r гэвэл a ба b-гийн хамгийн их ерөнхий хуваагч нь b ба r-ийн хамгийн их ерөнхий хуваагчтай тэнцүү байдаг. Энэхүү шинж чанарыг ашиглан цааш b-г r-д хуваахад гарах үлдэгдлийг олох гэх мэтээр явсаар үлдэгдэл нь 0 болох хүртэл үргэлжлүүлэн a ба b-гийн хамгийн их ерөнхий хуваагчийг олж болдог. Энэ аргыг олон гишүүнтийг хуваах Эвклидийн алгоритм гэж нэрлэдэг.

Эвклидийн алгоритмын давуу тал хэрэглээ

Эвклидийн алгоритмийг олон гишүүнтийн хамгийн их ерөнхий хуваагчийг олоход ашиглана. Энэ алгоритмыг ашигласнаар програмын ажиллах хурд нэмэгдэнэ. Эвклидийн алгоритмыг хэрэглэх явцдаа алхам бүрд өмнөх алхмынхаа хоёр тоог хадгалахаас гадна эдгээр тоонд харгалзах коэффициентүүдыг хадгалж байх хэрэгтэй.

Эвклидийн алгоритм нь дараах програмчлалын рекурсив загварын дагуу тусгагдана.

$\gcd(a,b):={\text{if}}\;b=0\;{\text{then}}\;a\;{\text{else}}\;\gcd(b,{\text{rem}}(a,b))$.

Програмчлалд үлдэгдэл олох алгоритмыг доорх загварын дагуу олно.

$r_{0}:=a;\quad r_{1}:=b;\quad i:=1;$
while $r_{i}\neq 0$ do

$r_{i+1}:={\text{rem}}(r_{i-1},r_{i});\quad i:=i+1;$

end do;
return $(r_{i-1}).$

Бид a(x) and b(x) хоёр олон гишүүнтийн нь хамгийн их ерөнхий хуваагчийг олохыг хүсэж байгаа гэж бид бодъё

$\deg(b(x))\leq \deg(a(x))\,.$

2 олон гишүүнт q(x) and r(x)-ээс аль тохирохыг нь олно. (Алгоритм хуваах хэсгийг үзэх)

• $a(x)=q_{0}(x)b(x)+r_{0}(x)$
• $\deg(r_{0}(x))<\deg(b(x))$

Эвклидийн алгоритм ашигласан жишээ

Бодлого 1: f(x)= t6+t5+t4−3t2+2t−6 ба g(x)= t5+3t2−2t+2 –ийн Х.И.Е.Х- ийг Эвклидийн алгоритмээр ол. 

Бодолт: f(x) -г g(x)-д хуваахад d(x)= t4−3t2−4t2+2t−8 гарч t+1 үлдэнэ. Бид үлдэгдэл нь 0 хүртэл хуваах учир g(x)-г эхний ноогдворын бүхэл үлдэгдэлдээ d(x) хуваана. Ийм зарчмаар үлдэгдэл нь 0 болтол хуваана.

(t6+t5+t4−3t2+2t−6) / (t5+3t2−2t+2) = (t4−3t2−4t2+2t−8) * (t+1)

(t5+3t2−2t+2) / (t4−3t2−4t2+2t−8) = (13t3+13t2+26) * ( t+3)

(t4−3t2−4t2+2t−8) / (13t3+13t2+26) = (−4t3−4t2−8) * ( t/13-4/13)

Хариу: Х.И.Е.Х нь ( t/13-4/13 )

Бодлого 2: f(x)=x4+3x3−x2−4x−3, g(x)=3x3+10x2+2x−3 хоёр олон гишүүнтийн Х.И.Е.Х-ийг Эвклидийн алгоритмээр ол.

Бодолт: Эвклидийн алгоритм хэрэглэх явцад хуваах үйлдлийг хялбар болгох зорилгоор хуваалтийн явцад хуваагч хуваагдагчийг тоогоор(коэффициентээр) үржүүлэх хуваах аргыг хэрэглэе. Энэ үйлдэл үлдэгдэл болох олон гишүүнтийн зэрэгт нөлөөлөхгүй. ХИЕХ зөвхөн коэффициентийн нарийвчлалтайгаар тодорхойлогдох ба ноогдвор өөрчлөгдөнө. Энэ байдал ХИЕХ олоход харшлахгүй.

F(x)-ийг 3-аар g(x)-д хуваая.

( 3x4+9x3−3x2−12x−9) / (3x3+10x2+2x−3 ) = (3x3+10x2+2x−3)) * (x+1)

(3x3+10x2+2x−3)-ийг хасхад 5x2+25x+30 гарна. Үүнийг 5-д хуваахад үлдэгдэл r1(x)= x2+5x+6 болно. g(x)-ийг r1(x) үлдэгдэлд хуваая.

(3x3+10x2+2x−3) / (x2+5x+6) = (9x+27) * ( 3x−5)

Үүнийг 9-д хуваасны дараа 2-аао үлдэгдэл r2(x)=x+3 болно. r1(x)= r2(x) (x+2) тул өмнөх үлдэгдэл бүтнээр хуваагдах үлдэгдэл r2(x) учраас тэр Х.И.Е.Х болно. Иймд x+3=(f(x), g(x)) болно.

Олон гишүүнтийг үржүүлэх

- Олон гишүүнтийн үржвэр нь хэд хэдэн тодорхой шинж чанарыг агуулдаг.

Бодлого

f,g,h ∈ R[x] гэсэн олон гишүүнтийг авч үзье. Дараах шинж чанарыг агуулдаг болохыг харна уу?

1. Үржвэр нь гишүүдийн байр солигдсон ч ижил

2. Үржвэр нь f(gh)=(fg)h байдаг

3. Үржвэр нь үржигдэхүүнийг хаалтаас гаргах аргаар задлахад f(g+h)=fg+fh байна.

4. Хэрэв 0 байвал f ∈ R[X] Болох тохиолдолд 0f=0 байна.

5. Хэрэв 1 гол гишүүнтэй олон гишүүнтийг заах юм бол f ∈ R[X] ийн бүх тохиолдолд 1f=1 байна.

6. Хэрэв fg=0 байхад f=0 эсвэл g=0 байна.

7. Зэрэг нь үржигдэхүүнд нэмэгддэг:

deg(fg)=degf+degg

f ∈ R[X] олон гишүүнт дээр f -ийн илэрхийлэл дэх тодорхойгүй х-ийн бодит тоог орлуулахаар f(x) тогтооход бүтцийг үүсгэнэ. Жишээ нь хэрэв f=1+X^2-3X^2 нь f(1)=-1 ба f(√2)=3-6√2 болно.
f ∈ R[X] олон гишүүнт.
Хэрэв f(x) = 0 байвал x ∈ R бодит тоог f -ийн 0 гэж нэрлэнэ. Үүний 0 үүд нь бодиж эсвэл нийлмэл хувиргалт (өөрчлөлт)-тэй хос тоо байна. Хэрэв f(x) = 0 байвал түүний нийлмэл хос тоо нь 0 байна.

Алгоритмыг хуваах

f = qg байх q ∈ R[X] олон гишүүнт байвал g ∈ R[X] олон гишүүнт нь f ∈ R[X] олон гишүүнтэд хуваагддаг. Хэрэв g|f байвал f = 0 эсвэл байна. Хэрэв fg = 0 байвал f = 0 эсвэл g = 0 байна. Энэ 0 биш олон гишүүнтээр хувааж болно.

Бодлого f, g ∈ R[X] олон гишүүнт. Хэрэв f|g ба g|f байвал degf = degg болно. Олон гишүүнтийн урт сунжирсан хуваагдлын олонлог байна. Энэ нь бүхэл тоонд хамаатай.

Теорем g ≠ 0 тай f, g ∈ R[X] олон гишүүнтийг авч үзье. f = qg + r ба deg r < deg g байвал q, r ∈ R[X] гэсэн онцгой олон гишүүнт байна.
Батлах нь: Бид эхлээд q-ийн оршин байх эсэхийг батална. Хэрэв deg g > deg f байвал q = 0 ба r = f байна.

a_m ≠0 байхад f= a_0 +..+a_m X^m
b_n ≠0 байхад f= b_0 +..+b_n X^n

d = m - n ≥ 0 бүхэл тоог тодорхойл.

Бид d дэх функцийг хэрэглэнэ.

Үндсэн алхам: d = 0 үед авч үзье. Дараа нь m = n Бид q = a_m / b_m ба r = f - qg -ийг авч үзье.

r үгүй тохиолдолд X^m -ийн коэффициент ба b_m ≠ 0 учраас q сайн тодорхойлогдоно. Энд deg r < m = deg g

Индукцийн үе шат

d < k ямар ч үед зөв байх ба d = k байхыг авч үзье. Тиймээс m = n + k. f_1=f-(a_m/b_n)X^m-n -д авч үзье. deg r < deg g ба f_1=q_1 g -тэй байна. q=q_1+(a_m/b_n)X^(m-n) тодорхойлолтоос f=f_1+a_m/b_n X^(m-n) q=(q_1+a_m/b_n X^(m-n) )g+r

Үр дүн нь d = k –ийн хувьд үнэн байна.

Эцэст нь бид онцгой байна гэдгийг баталья deg R < deg g ба deg r < deg g тэй f = qg + r = Qg + R байна гэж бодъё.

g нь R - r хуваагдахад R - r = (q - Q)g байна. Хэрэв R - r = 0 байвал R = r байна. deg(R - r) < deg g учраас g(q - Q) = 0 байх тохиолдолд g ≠ 0 учир q - Q = 0 байх ба Q = q байна.

Теорем дэх q ба r олон гишүүнт нь ноогдвор буюу үлдэгдэл гэж нэрлэнэ. f, g ∈ R[X] өгөгдөлд q, r нэг нэгээрээ хуваагдахыг бид дараахь жишээнээс үзэж болно.

Жишээ

f = X^3 + X^2 - 3X - 3 ба X^2 + 3X + 2 -ыг авч үзье. Дараа нь f_1 = f - X_g = -2X^2 - 5X - 3 байна. g -ээс бага зэрэг бүхий f_2 = f_1 + 2g = X + 1 -ыг авч үзъе.

q = X - 2 ба r = 1 + X байхад f=f_1+X_g=f_2+(X-2)g=(X-2)g+(1+X) болно.

Бодлого f олон гишүүнтийн хуваагдлын g ноогдвор ба r үлдэгдлийг олъё.

• f=3+X+〖2X〗^2+X^3-X^4,g=1+X
• f=〖2X〗^2+〖3X〗^3,g=1-3X+〖2X〗^2
• f=-1+X+X^3+〖3X〗^4,g=2-X-〖2X〗^2-〖2X〗^3
• f=2X-〖3X〗^2-〖2X〗^3-〖2X〗^4,g=-2-X^2+〖2X〗^3
• f=-3-2X-〖2X〗^2-〖3X〗^3,g=-1-3X-〖3X〗^2+〖3X〗^3

Үр дүн: Хэрэв олон гишүүнт нь -д хуваагдавал -ийн 0 бодит тоо юм.

Баталгаа: Хэрэв байвал дэх мэтийн зарим олон гишүүнт оршин тогтоно. Иймээс ба нь f-ийн тэг утга байна. f-ийн 0 утга нь байна гэж үзье. Алгоритмын хуваагдалыг ашиглан бүхий зэргийн онцлог олон гишүүнт байна. Энэ нь тогтмол байна гэсэн үг юм. Нэгдмэл бүтцийн хувьд . -д дүгнэлт гаргахад х нь f-д хуваагдахад r=0 болохыг харна.

Үр дүн: n зэргийн 0 биш олон гишүүнт ихэнх нь 0 дээр байж болно.

Олон гишүүнтийг Эвклидийн алгоритмаар бодох нь

R[X] г Эвклидийн алгоритмыг ашиглан 2 полиномд хамгийн их хуваагчийн утгыг тооцож олно.

f, g ∈ R[X] бол d ∈ R[X] полином гэх ба f болон g хоёуланг хуваадаг хамгийн их зэргийг хамгийн их хуваагчийн утга гэнэ. d нь тэгтэй биш скаляраар үржигдэнэ. 0 ≠ c ∈ R ийг тэгтэй тэнцүү биш гэж үзээд d бол f, g ∈ R[X] н хамгийн их хуваагчийн утга гэвэл cd болно гэсэн үг.

g=0 үед өгөгдсөн f болон g полиномд deg r < deg g гэж үзээд q, r полиномын хуваагчийн утга нь f = qg +r болно.

Хэрэв r болон g - н хамгийн их хуваагчийн утга гэвэл f болон g полиномын хамгийн их хуваагч болно. Энэ нь бүхэл тооны хамгийн их хуваагчийн утгад батлагдана. Эвклидийн алгоритмд ч гэсэн адилхан биелнэ.

Бодлого: g - н утга 0-с ялгаатай үед ---- 2 полиномын хуваагчийн хамгийн их утгыг ол.

Хариулт: Эвклидийн алгоритмээр бодвол:

1. F = f, G = g гэе

2. deg r < deg G үед F = qG + r болох ба q,r полиномыг хуваагчийн алгоритмээр олно.

3. r = 0 бол G = g нь хамгийн их хуваагчийн утга болно.

4. r - н утга тэгээс ялгаатай гэж үзвэл F - г G- р орлуулаад G -г r - р орлуулаад 2 - р хэсэг руу очно.

G - н утга зэрэг нэмэгдэх тусам буурна гэдгийг санаарай.

d = fr + gs -г Эвклидийн алгоритмээр бодохын тулд f , g - г d-д хуваана. ингээд f , g-н хамгийн их хуваагчийн утга нь тэдгээрийн үржвэр гэдгийг баталж болно. d1, d2 нь хамгийн их хуваагчийн утга болох ба d1/d2, d2/d1 гэж үзээд Бодлого 5,3 - тай адил зэрэгтэй байгаа учраас d1 = cd2 болж с нь тогтмол тоо байна.

Тогтмол утга тус бүрээр үржүүлэхээс зайлсхийхийн тулд нэмэлт нөхцлийг d дээр оруулсанаар хамгийн их хуваагчийн утгыг олох боломжтой болно.

Хамгийн их хуваагчийн утга нь монотон бөгөөд зэргийн хамгийн их коэффициент нь 1 - с их байна гэсэн үг юм.