1-tema. Algoritm túsinigi hám onnan paydalanıw Reje

Evklid algoritmi – pútin sanlar hám bir ózgeriwshili eki kóp aǵzalınıń eń úlken ulıwma bóliwshisini tabıw usılı. Dáslep Evklidtiń «Tiykarlar» kitabında eki kesindiniń ulıwma ólshemin tabıw usılı sıpatında geometriyalıq formada bayan etilgen edi. Putin sanlar halqasında hám, bir ózgeriwshili kóp aǵzalalar halqasında hám eń úlken ulıwma bóliwshini tabıwdıń Evklid algoritmi Evklid halqalarındaǵı bir ulıwma algoritmniń dara jaǵdayı boladı.
Pútin sanlar ushın Evklid algoritmi tómendegiden ibarat: a hám b – pútin san hám a>b bolsın dep aytayıq. Onda a nı b ǵa qaldıq menen bólemiz. Tolıq emes q₁ bólinbe hám r₁ qaldıq payda boladı. Bunda 0< r₁ 1 ge qaldıq menen bólemiz.Tolıq emes bólinbe q₂ hám r₂ qaldıq payda boladı. Bunda 0< r₂ < r₁ . Soń r₂ ni r₁ ge qaldıq mene bólemiz h.t.b. Sonda tómendegi teńlikler shınjırı payda etemiz:
a=bq₁+r₁ , (0< r₁ b=r₁q₂ +r₂, (0< r₂ 1),
r₁ = r₂q₃ +r₃, (0< r₃ 2), (*)
…………………………
r_n-2 = r_n-1q_n +r_n, (0< r_n n-1),
r_n-1 = r_nq_n+1 +r_n+1, (r_n+1 =0).
Bunda bir neshe qádemnen keyin nol`ge teń bolǵan (r<sub>n+1</sub> =0) náwbettegi qaldıq payda boladı. Sebebi qaldıqlar izbe-izligi teris bolmaǵan pútin sanlardıń kemeyiwshi izbe-izligi, yaǵnıy b> r<sub>1</sub>> r<sub>2</sub>> r<sub>3</sub>>…> r<sub>n</sub>> r<sub>n+1</sub> bolǵanı ushın shekli sandaǵı qádemlerden soń nol` menen tamamlanıwı kerek. Bul jaǵdayda a hám b sanlarınıń eń úlken ulıwma bóliwshisi izbe-iz bóliwdiń (*) sxemasındaǵı nol`den ózgeshe eń keyingi r<sub>n</sub> qaldıqqa teń boladı.
Mısal(Exampl). Berilgen 1981 hám 378 sanlarınıń eń úlken ulıwma bóliwshisin tabıń. İzbe-iz bólemiz: 1981=378·5+91 14=7·2+0. Nol`den ózgeshe eń keyingi qaldıq 7. Sonıń ózi 1981 hám 378 sanlarınıń eń úlken ulıwma bóliwshisi boladı.
Eki hám kóp aǵzalınıń eń úlken ulıwma bóliwshisin tabıwda hám Evklid algoritmi nı ǵa , onnan keyin tı birinshi qaldıqqa, onnan soń ti ekinshi qaldıqqa hám t.b. izbe-iz bóliwden ibarat:
= + ,
= + ,
= + ,

………………………..

= +
= +0.
Qaldıqlardıń dárejeleri natural sanlar bolıwı menen birge kemeyip barǵanı ushın bir neshe qádemden keyin nol`ge teń bolǵan qaldıqqa jetip kelemiz. Nol`den ózgeshe bolǵan eń keyingi qaldıq hám kóp aǵzalarınıń eń úlken ulıwma bóliwshisi boladı.