Nizomiy nomidagi tdpu fizika-matematika fakulteti matematika o`qitish metodikasi yo`nalishi 4-bosqich talabasi

NIZOMIY NOMIDAGI TDPU FIZIKA-MATEMATIKA FAKULTETI MATEMATIKA O`QITISH METODIKASI YO`NALISHI 4-BOSQICH TALABASI Qo`shayeva Sevara Umidjon Qizining TANLOV FAN: ELEMENTAR MATEMATIKADA YECHILMAGAN MUAMMOLAR FANIDAN TAYYORLAGAN MUSTAQIL ISHI

Diofant tenglamalari, eng katta umumiy bo‘luvchi va Evklid algoritmi.


Avvalgi suhbatimizda:

(1)
ko‘rinishdagi ikki noma’lumli bitta tenglamaga misollar ko‘rgandik. Agar bunday tenglamaning koeffisientlari ham butun son bo‘lib, faqat butun yechimlari izlansa, u Diofant tenglamasi deb ataladi.

(1) tenglama koordinatalar tekisligida to‘g‘ri chiziqni tasvirlagani uchun, u chiziqli tenglama deyiladi. Biz o‘rganayotgan holda esa, chiziqli Diofant tenglamasi deb ataladi.

Endi (1) ko‘rinishdagi Diofant tenglamalari bilan yaqinroq tanishaylik. Qarangki, ular ikki butun sonning eng katta umumiy bo‘luvchisi (qisqacha EKUB)

tushunchasi bilan chambarchas bog‘liq ekan.

Teorema. Agar (1) Diofant tenglamasi yechimga ega bo‘lsa, c soni a va b ning EKUBiga qoldiqsiz bo‘linadi. Aksincha, c soni a va b larning EKUBiga qoldiqsiz bo‘linsa, (1) Diofant tenglamasi yechimga ega bo‘ladi.

Teoremada, garchi Diofant tenglamasining yechimi qanday topilishi haqida hech narsa deyilmayotgan bo‘lsada, uning isboti yechish usulini berishini ko‘ramiz. Hozircha esa a va b koeffisientlarning EKUBi qanday topilishi ustida bosh qotiraylik. Birinchi usul – a va b sonlarni tub ko‘paytuvchilarga ajratish. Lekin bu qulay usul emas. Aytaylik, a sonining biror tub ko‘paytuvchisini topish uchun bu sonni ketma-ket 2, 3, 5, 7, 11 va hokazo tub sonlarga bo‘la boshlash va bu ishni to tub ko‘paytuvchiga yo‘liqquncha davom ettirish kerak. Masalan, bo‘lsa, bo‘lish jarayoni 71 ga borganda to‘xtaydi. Shundan so‘ng bu ish bo‘linma ustida davom ettirilishi lozim. Ikki-uch xonali sonlar uchun-ku, tub ko‘paytuvchilarni topish u qadar qiyin emas, ammo vazifani 5-6 xonali sonlar uchun bajargudek bo‘lsak, ancha hisob-kitob talab etadi. Yana ustiga-ustak, bu ishni b ustida ham bajarish lozim. Qadimgi yunon olimi Evklid o‘zining “Negizlar” kitobida EKUBni topishning ancha o‘ng‘ay usulini bayon etgan.

Bu usul Evklid algoritmi deb ataladi. (E’tibor bering: algoritm so‘zi Muhammad ibn Muso al-Xorazmiy nisbasidan olingan, Evklid esa undan 1200 yil avval yashab o‘tgan. Gap shundaki, al-Xorazmiyning o‘nli sanoq sistemasiga bag‘ishlangan “Hind hisobi haqida” kitobida algoritm g‘oyasi, ya’ni tayin natija bilan yakunlanadigan aniq farmoyishlar tizimi keng va izchil qo‘llangan. “Negizlar”dagi usul ham shu talabga javob bergani bois u Evklid algoritmi deb atalgan. Natijada bitta nomda ikki buyuk matematik xotirasi abadiylashgan).

Evklid algoritmi. Ikki butun musbat sonning EKUBini topish uchun:

1-qadam. Berilgan sonlarni taqqosla.

Ular teng bo‘lsa,

6-qadamga o‘t, aks holda 2-qadamga o‘t.

2-qadam. Birinchi sonni ikkinchisiga bo‘l.

3-qadam. Qoldiqqa boq: agar u 0 ga teng bo‘lsa, 6-

qadamga, aks holda keyingi qadamga o‘t.

4-qadam. Ikkinchi sonni birinchi son deb, qoldiqni

ikkinchi son deb ol.

5-qadam. 2-qadamga o‘t.

6-qadam. Ikkinchi son izlanayotgan EKUB bo‘ladi.

Misol. Berilgan sonlar 7560 va 1834 bo‘lsin. Algoritmga muvofiq, 7560 ni 1834 ga bo‘lamiz. Bo‘linma 4, qoldiq 224. 1834 ni 224 ga bo‘lamiz. Bo‘linma 7, qoldiq 42. 224 ni 42 ga bo‘lamiz. Bo‘linma 5, qoldiq 14. 42 ni 14 ga bo‘lamiz. Bo‘linma 3, qoldiq 0.

Demak, 7560 bilan 1834 ning EKUBi 14 ekan. Mashq. Natijani 7560 va 1834 sonlarini tub ko‘paytuvchilarga ajratib, tekshirib ko‘ring. Endi nima uchun Evklid algoritmi chindan EKUB ni

aniqlashini asoslaylik. Birinchidan, bir sonni ikkinchi songa bo‘lganda, qoldiq har doim bo‘luvchidan kichik chiqadi. Ya’ni, Evklid algoritmida qoldiqlar qadamba-qadam kamayib boradi.

Shuning uchun chekli qadamdan so‘ng qoldiq albatta 0 ga teng bo‘ladi.

Ikkinchidan, yuqoridagi hisob-kitoblarni ixcham qilib

yozaylik:

(2)

(3)

(4)

(5)

So‘ng bu “zinapoya” bo‘yicha “yuqoriga chiqib

tushamiz”.

Yuqoriga:

(5) tenglikka ko‘ra, 42 soni 14 ga bo‘linadi. Demak,

(4) tenglikka ko‘ra, 224 soni 14 ga bo‘linadi. Demak,

(3) tenglikka ko‘ra, 1834 soni 14 ga bo‘linadi. Demak,

(2) tenglikka ko‘ra, 7560 soni 14 ga bo‘linadi.

Shunday qilib, 14 soni 7560 va 1834 ning umumiy

bo‘luvchisi ekan.

Quyiga: soni 7560 va 1834 ning biror umumiy

bo‘luvchisi d bo‘lsin. Ya’ni, 7560 ham, 1834 ham d ga

bo‘linsin. U holda,

(2) tenglikka ko‘ra, d ga 224 bo‘linishi lozim. U holda,

(3) tenglikka ko‘ra, d ga 42 bo‘linishi lozim. U holda,

(4) tenglikka ko‘ra, d ga 14 bo‘linishi lozim.

Demak, 14 d dan katta bo‘lsa kattaki, kichik emas. Shunday qilib, 14 chindan 7560 va 1834 sonlari umumiy bo‘luvchilarining eng kattasi ekan!

Bu yerda tayin bir misol uchun o‘tkazilgan mushohada

umumiy holda ham o‘rinli. Yuqori sinf o‘quvchilariga

“yuqoriga va quyiga” mushohadasini umumiy holda, ya’ni

berilgan sonlar va bo‘lganda bajarib, Evklid algoritmini to‘liq isbotlashni tavsiya etamiz. Bunda “zinapoya” mana bunday ko‘rinishda bo‘ladi:

– bo‘linma , qoldiq ,

– bo‘linman , qoldiq ,

– bo‘linma , qoldiq ,

...

– bo‘linma , qoldiq

– bo‘linma , qoldiq ,

– bo‘linma , qoldiq 0 .

Endi Evklid algoritmining Diofant tenglamasiga

aloqasini ko‘raylik. Buning uchun (2)-(4) tengliklarni

mana bunday qilib yozib olamiz:

(2`)

(3`)

(4`)
So‘ng ko‘rsatilgani bo‘yicha sonlarni o‘ziga teng ifodalar bilan almashtirish amalini bajaramiz. Bunda “pastdan yuqoriga” tomon harakat qilamiz.