Algoritmning asosiy xossalari

1.2 Eng katta umumiy bo`luvchi (EKUB)

Ta`rif: a<sub>1</sub>,a<sub>2</sub>,a<sub>3</sub>,…,a<sub>n</sub>Z sonlarning umumiy bo`luvchisi deb, berilgan sonlarning har biri bo`linadigan dZ songa aytiladi.

Berilgan sonlarning umumiy bo`luvchi shu sonlarning barcha umumiy bo`luvchilariga bo`linsa, bu umumiy bo`luvchi berilgan sonlarning eng katta umumiy bo`luvchi deyiladi.

Berilgan sonlarning eng katta umumiy bo`luvchisi EKUB(a₁,a₂,a₃,…,a_n) kabi belgilanadi.

Eng katta umumiy bo`luvchining ta`rifidan ushbu muhim xossa kelib chiqadi:

1. 
   • agar d=EKUB(a₁,a₂,a₃,…,a_n) bo`lsa, a<sub>1</sub>, a<sub>2</sub>, a<sub>3</sub>, … , a<sub>n</sub> sonlarning barcha umumiy bo`luvchilari to`plami d sonining barcha bo`luvchilaridan iborat bo`ladi.
   
2. 
   • agar d=EKUB(a₁,a₂,a₃,…,a_n) bo`lsa, u holda d=EKUB(a<sub>1</sub>,a<sub>2</sub>,a<sub>3</sub>,…,a<sub>n</sub>,0) bo`ladi. Aksincha, agar d=EKUB(a₁,a₂,a₃,…,a_n,0) bo`lsa, d=EKUB(a<sub>1</sub>,a<sub>2</sub>,a<sub>3</sub>,…,a<sub>n</sub>) bo`ladi.
   

Agar EKUB(a₁,a₂,a₃,…,a_n)=1 bo`lsa, a<sub>1</sub>, a<sub>2</sub>, a<sub>3</sub>, … , a<sub>n</sub> sonlar “o`zaro tub sonlar” deyiladi.

Endi berilgan sonlarning eng katta bo`luvchisini qanday topish mumkinligi haqida fikr yuritamiz.

a,bZ, a ≠ 0, b ≠ 0 sonlar uchun: c₁, c₂, c₃, …, c_n-1, c_n ketma-ketlikni quyidagi tuzamiz:

c₁=a, c₂=b deb olamiz. Agar bo`lsa, EKUB(a,b)=b bo`ladi. Aks holda c₁ ni c₂ ga bo`lishda hosil bo`lgan qoldiqni c₃ deb olamiz, c₂ ni c₃ ga bo`lishdagi qoldiqni c₄ deb olamiz va hokazo.

Bunday qoldiqli bo`lishlar ketma-ketligini qulaylik uchun tengliklar zanjiri ko`rinishida bunday yozamiz:

c₁=c₂q₂+c₃

c₂=c₃q₃+c₄

c₃=c₄q₄+c₅

…………

c_n-2=c_n-1q_n-1+c_n

c_n-1=c_nq_n
qoldiqli bo`lish natijasida qoldiqlar uchun c<sub>2</sub>>c<sub>3</sub>>c<sub>4</sub>… munosabat o`rinli bo`ladi, bundan tashqari qoldiqlar nomanfiy sonlardir. Shu sababli bu qoldiqlar orasida nolga teng bo`ladigani albatta uchraydi. c_n uchun noldan farqli oxirgi qoldiqni olamiz. Bu holda c_n-1 soni c_n ga bo`linishi ravshan.

Hosil qilingan c₁, c₂, c₃, …, c_n-1, c_n ketma-ketlik a va b sonlari uchun Evklid ketma-ketligi deyiladi.

Ketma-ket qoldiqli bo`lish yordamida bunday ketma-ketlikni hosil qilish usuli Evklid algoritmi deb ataladi.

Misol. 78 va 24 sonlari uchun Evklid ketma-ketligini tuzing.

Yechilishi.

78=244+18

24=181+6

18=63+0

Bundan, izlangan ketma-ketlik hosil bo`ladi: 78, 24, 18, 6.

Теорема. a va b (a≠0,b≠0) sonlar uchun tuzilgan Evklid ketma-ketligi c₁, c₂, c₃, …, c_n-1, c_n ning oxirgi hadi a va b sonlarining eng katta umumiy bo`luvchisi bo`ladi: c_n=EKUB(a,b).

Isbot: c₁, c₂, c₃, …, c_n-1, c_n sonlar o`zaro yuqorida keltirilgan qoldiqli bo`lish munosabati bilan bog`langan. Tengliklar zanjiri orqali yuqoriga harakatlanib, quyidagilarni aniqlaymiz:

c_n-1=c_nq_n munosabatdan ;

c_n-2=c_n-1q_n-1+c_n munosabatdan ;

c_n-3=c_n-2q_n-2+c_n-1 munosabatdan ;

va hokazo

va .

Bunda c₁=a va c₂=b. Shunday qilib, c_n — a va b sonlarining umumiy bo`luvchisi.

x soni a va b sonlarining boshqa bir umumiy bo`luvchisi bo`lsin. Evklid algoritmidagi qoldiqli bo`lishlar zanjirida pastga qarab harakatlanib, quyidagilarni aniqlaymiz:

c₁=c₂q₂+c₃ ga teng kuchli c₃₌c₁-c₂q₂ munosabatdan

c₂=c₃q₃+c₄ ga teng kuchli c₄₌c₂-c₃q₃ munosabatdan

mulohazalarni davom ettirib,

c_n-2=c_n-1q_n-1+c_n ga teng kuchli c_n= c_n-2-c_n-1q_n-1 munosabatdan ga ega bo`lamiz.

Shunday qilib, ta`tifga ko`ra, c_n=EKUB(a,b).

Misol. EKUB(42598, 2014) ni toping.

Yechilishi. Berilgan sonlar uchun Evklid ketma-ketligini tuzamiz. Qoldiqli bo`lishlar ketma-ketligini quyidagi sxema bo`yicha bajarish qulay:

_42598  2014

4028 21

_ 2318

2014

_ 2014  304

1824 6

_ 304  190

190 1

_ 190114

114 1

_ 114  76

76 1

_ 76  38

76 2

0

Javob: EKUB(42598, 2014) = 38.

Mashqlar.

Evklid algoritmi yordamia quyidagi sonlarning EKUB ini toping:

1) 645 va 381; 2) 846 va 246; 3) 15283 va 10013; 4) 6188 va 4709 ;

5) 4005 va 2581.

Javob: 1) 3; 2) 6; 3) 527; 4) 17; 5) 89.
1.3 Eng kichik umumiy karrali (EKUK)

Ta`rif: a<sub>1</sub>, a<sub>2</sub>, a<sub>3</sub>, … , a<sub>n</sub>Z sonlarning har biriga bo`linadigan son bu sonlarning umumiy karralisi (bo`linuvchisi) deyiladi. Berilgan sonlarning istalgan umumiy karralisining bo`luvchisi bo`lgan umumiy karralisi bu sonlarning eng kichik umumiy karralisi deyiladi.

Berilgan sonlarning eng kichik umumiy karralisi h=EKUK(a,b) kabi belgilanadi.

Teorema. Agar d=EKUB(a,b), d≠0 bo`lsa, u holda h=EKUK(a,b)= bo`ladi.

Isbot: h soni a va b sonlarining umumiy karralisi bo`lgani uchun va bo`ladi.

x — a va b sonlarining istalgan boshqa bir umumiy karralisi bo`lsin, u holda x=au, x=bv (u,vZ) bo`ladi. Bundan au=bv kelib chiqadi. Bu tenglikning har ikki tomomini d ga bo`lsak: . va sonlar o`zaro tub bo`lgani uchun u soni ga bo`linadi. Shuning uchun , tZ. Bundan, . Shunday qilib, x doni ga bo`linadi. Demak, x soni h ga ham bo`linadi.

Misol. EKUK(462,252) ni toping.

462 = 252⋅1 + 210,

252 = 210⋅1 + 42,

210 = 42⋅5.

demak, EKUB(462,252) =42