Xulosa. Foydalanilgan adabiyotlar


Eng katta umumiy bo`luvchi (EKUB)


Download 203.5 Kb.
bet3/10
Sana06.04.2023
Hajmi203.5 Kb.
#1331465
1   2   3   4   5   6   7   8   9   10
Bog'liq
1-Evklid algoritmi

2. Eng katta umumiy bo`luvchi (EKUB)
Ta`rif: a1,a2,a3,…,an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(a1,a2,a3,…,an) kabi belgilanadi.
Eng katta umumiy bo`luvchining ta`rifidan ushbu muhim xossa kelib chiqadi:

  1. • agar d=EKUB(a1,a2,a3,…,an) bo`lsa, a1, a2, a3, … , an sonlarning barcha umumiy bo`luvchilari to`plami d sonining barcha bo`luvchilaridan iborat bo`ladi.

  2. • agar d=EKUB(a1,a2,a3,…,an) bo`lsa, u holda d=EKUB(a1,a2,a3,…,an,0) bo`ladi. Aksincha, agar d=EKUB(a1,a2,a3,…,an,0) bo`lsa, d=EKUB(a1,a2,a3,…,an) bo`ladi.

Agar EKUB(a1,a2,a3,…,an)=1 bo`lsa, a1, a2, a3, … , an 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: c1, c2, c3, …, cn-1, cn ketma-ketlikni quyidagi tuzamiz:
c1=a, c2=b deb olamiz. Agar bo`lsa, EKUB(a,b)=b bo`ladi. Aks holda c1 ni c2 ga bo`lishda hosil bo`lgan qoldiqni c3 deb olamiz, c2 ni c3 ga bo`lishdagi qoldiqni c4 deb olamiz va hokazo.
Bunday qoldiqli bo`lishlar ketma-ketligini qulaylik uchun tengliklar zanjiri ko`rinishida bunday yozamiz:
c1=c2q2+c3
c2=c3q3+c4
c3=c4q4+c5
…………
cn-2=cn-1qn-1+cn
cn-1=cnqn

qoldiqli bo`lish natijasida qoldiqlar uchun c2>c3>c4… munosabat o`rinli bo`ladi, bundan tashqari qoldiqlar nomanfiy sonlardir. Shu sababli bu qoldiqlar orasida nolga teng bo`ladigani albatta uchraydi. cn uchun noldan farqli oxirgi qoldiqni olamiz. Bu holda cn-1 soni cn ga bo`linishi ravshan.


Hosil qilingan c1, c2, c3, …, cn-1, cn 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 c1, c2, c3, …, cn-1, cn ning oxirgi hadi a va b sonlarining eng katta umumiy bo`luvchisi bo`ladi: cn=EKUB(a,b).
Isbot: c1, c2, c3, …, cn-1, cn sonlar o`zaro yuqorida keltirilgan qoldiqli bo`lish munosabati bilan bog`langan. Tengliklar zanjiri orqali yuqoriga harakatlanib, quyidagilarni aniqlaymiz:
cn-1=cnqn munosabatdan ;
cn-2=cn-1qn-1+cn munosabatdan ;
cn-3=cn-2qn-2+cn-1 munosabatdan ;
va hokazo
va .
Bunda c1=a va c2=b. Shunday qilib, cna 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:
c1=c2q2+c3 ga teng kuchli c3=c1-c2q2 munosabatdan
c2=c3q3+c4 ga teng kuchli c4=c2-c3q3 munosabatdan
mulohazalarni davom ettirib,
cn-2=cn-1qn-1+cn ga teng kuchli cn= cn-2-cn-1qn-1 munosabatdan ga ega bo`lamiz.
Shunday qilib, ta`tifga ko`ra, cn=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.


3. Eng kichik umumiy karrali (EKUK)
Ta`rif: a1, a2, a3, … , an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.
xa 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.

Download 203.5 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8   9   10




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling