ІІ тарау. Евклид алгоритмінің қолданылуы
2.1. Бөлшектерді қысқарту.
Ең үлкен ортақ бөлгішті табу оңай көрінгенмен кей жағдайларда көбейткіштерге жіктеу арқылы табу қиындық тудырады, мәселен, үлкен жай сандарға ғана қысқаратын бөлшектерді қысқарту (немесе мүлдем қысқармайтын бөлшектерді анықтау). Бұндай тапсырма көп уақытты қажет ететін жұмыс. Ал ең үлкен ортақ бөлгішті есептеудің екі мың жылдан астам уақыт бойы белгілі болып келе жатқан Евклид алгоритмі жұмысты жеңілдетеді.
Мысалы:
2147 = 113 . ЕҮОБ (2147, 1577) = 19
1577 83
- 2147 1577
1577
- 1577 570 1
1140
- 570 437 2
437
- 437 133 1
399
- 133 38 3
114
- 38 19 3
38 2
0
Сонымен қатар алгебралық өрнектерді қысқарту үшін көбейткіштерді жіктеудің бірнеше әдістерін қолдануға тура келеді. Ал солардың ішінде топтау әдісін, әсіресе жаңа мүше енгізу әдісін қиындатылған есептерде қолдану оңай емес. Соның орнына Евклид алгоритмі жұмысты жеңілдетеді.
Мысалы:
a(x) = x4 − 4x3 + 4 x2 − 3x + 14 = (x2 − 5x + 7)(x2 + x + 2)
және b(x) = x4 + 8x3 + 12x2 + 17x + 6 = (x2 + 7x + 3)(x2 + x + 2).
a(x) көпмүшесін b(x) көпмүшесіне бөлгенде r0(x) = x3 + (2/3) x2 + (5/3) x − (2/3) қалдық қалады. Келесі қадам b(x)-ті r0(x) қалдығына бөлгенде r1(x) = x2 + x + 2 қалдық қалады. Соңында r0(x)-ті r1(x) қалдығына бөлгенде 0 қалдық береді, яғни r1(x) қалдығы a(x) және b(x) көпмүшелерінің ең үлкен ортақ бөлгіші болып табылады.
Достарыңызбен бөлісу: | 
