Reja kirish

1.2. FIBONACHCHI SONLARINING NAZARIY SONLI HOSSALARI

Dastlab Fibonachchi sonlarining bo`linishiga doir ayrim hossalarini ko`raylik.

Teorema. Agar n soni m ga bo`linsa, u holda u<sub>n</sub> ham u<sub>m</sub> ga bo`linadi.

Isbot: Faraz qilaylik, n soni m ga bo`linsin., ya`ni . Isbotda k bo`yicha qo`shiluvchi dan foydalanamiz.

k=1 uchun n=m p, shuning uchun bu holda u_n sonining u_m ga bo`linishi tabiiy. Faraz qilaylik, u<sub>mk</sub> soni u<sub>m</sub> ga bo`linsin. u_m(k+1) ni qaraymiz. hamda (1.18) asosida

.

Bu tenglikning o`ng tomonidagi birinchi qo`shiluvchining ga bo`linishi tabiiy. Ikkinchi qo`shiluvchi esa ga karrali, ya`ni qo`shiluvchi ga ko`ra u ham ga bo`linadi. Demak, ularning yig’indisi ham ga bo`linadi. Teorema isbot bo`ldi.

2. Biror m sonini olaylik. Agar unga bo`linadigan birorta Fibonachchi soni mavjud bo`lsa, u holda bunday ga bo`linadigan Fibonachchi sonlari yetarlicha darajada ko`p bo`ladi. Masalan, sonlarning barchasi ga bo`linadi.

Shuning uchun, berilgan m soniga ko`ra, unga bo`linadigan Fibonachchi sonlaridan hech bo`lmaganda bittasini topish mumkinmi? Degan savol tug’iladi. Bu sohadagi ishlar buning iloji borligini ko`rsatdi.

Faraz qilaylik, orqali k ni m ga bo`lganda hosil bo`ladigan qoldiq belgilangan bo`lsin. Fibonachchi sonlari orasidan m ga bo`lganda shunday qoldiq beradigan juftliklarni yozib olamiz:

(2.1)

Agar va juftliklarni hamda bo`lgan xoldagina teng bo`ladi desak, u holda m bo`lganda turli qoldiq beradigan juftliklar soni ta bo`ladi. Shuning uchun, agar (2.1.) ketma-ketlikning dastlabki hadlari olinsa, u holdla ularning ichida albatta tengllari mavjud bo`ladi.

Faraz qilaylik, (2.1) ketma-ketlikda takrorlanuvchi dastlabki juftlik bo`lsin. (1, 1) ning ham ana shunday juftlik ekanligini ko`rsatamiz. Buning teskarisini faraz qilaylik, ya`ni - birinchi takrorlanuvchi juftlik bo`lsin. (2.1) da unga teng bo`lgan juftlik ni topamiz.

va hamda va bo`lgani uchun, larni m gu bo`lganda qoldiqlar teng bo`lishi kerak, ya`ni . Ammo, bundan ekanligi kelib chiqadi, juftlik esa (2.1) ketma-ketlikda juftliklar ilgariroq uchraydi va shuning uchun, birinchi takrorlanuvchi juftlik emas. Bu esa bizning farazimizga zid. Demak, k birdan katta emas, ya`ni k=1. .

Shunday qilib, (1, 1) (2.1.) uchraydigan birinchi juftlik ekan. U t-chi o`rinda takrorlansin (ilgari yuritgan mulohazalarimizga ko`ra, ), ya`ni

.

Bu holat sonlarini m ga bo`lganimizda qoldiqda bir bo`lishini anglatadi. Ularning ayirmasi esa m ga qoldiqsiz bo`linadi. Ammo,

,

edi. Shuning uchun t-1-chi Fibonachchi soni m ga qoldiqsiz bo`linadi.

Biz bu bilan quyidagi teoremani isbotladik.

Teorema. Butun m soni qanday bo`lishidan qat`iy nazar, dastlabki ta Fibonachchi sonlari orasida m ga bo`linadigan hech bo`lmaganda bitta son mavjud.

Shuni alohida ta`kidlash kerakki, isbotlangan teorema aynan qaysi Fibonachchi sonlari m bo`linishi mumkinligini tasdiqlamaydi. U Fibonachchi sonlari orasida m ga bo`linadigan dastlabki sonning yetarlicha katta bo`lmasligini ko`rsatadi xalos.

(1, 1) ning (2.1) ketma-ketlikdagi dastlabki takrorlanuvchi juftlik ekanligidan, u_t dan boshlab, qoldiqlar ketma-ketligi boshidan boshlab takrorlana boshlaydi. Bu esa qoldiqlar ketma-ketligining davriyligidan dalolat beradi. Masalan, m=4 bo`lganda qoldiqlar ketma-ketligidagi quyidagicha bo`ladi:

1, 1, 2, 3, 1, 0. (2.2)

Bu holda davrning uzunligi 6 ga teng. Shunday qilib, agar n soni ko`rinishida bo`lsa, u holda ni 4 ga bo`lganimizda qoldiq birga teng bo`ladi. Agar n soni 6 ko`rinishida bo`lsa, qoldiq 2 ga, bo`lgan xolda esa 3 ga teng bo`ladi.

3. Fibonachchi sonlarining tabiati va bo`luvchilari haqidagi masala ham ancha diqqatga sazovor hisoblanadi. n soni murakkab va 4 dan farqli bo`lganda u_n soni ham murakkab bo`lishini isbotlaymiz.

Haqiqatdan ham, bunday n lar uchun deb yozish mumkin. Bu yerda hamda Aniqlik uchun deylik. Yuqorida isbotlangan teoremaga ko`ra, soni ga bo`linadi hamda . Demak, murakab son ekan.

4. Fibonachchi sonlarin o`rganishni davom ettirib, sonlar nazariyasidagi bizning mavzuimizga oid ayrim ma`lumotlarni keltirib o`tamiz.

Dastlab a va b sonlari uchun eng katta bo`luvchini topish masalasini ko`raylik.

a ni b ga qoldiq bilan bo`lamiz. Bunda bo`linma q₀ va qoldig’i r₁ bo`lsin. Ko`rinib turibdiki,

Shuni ta`kidlash joizki, a bo`lganda q₀=0.

So`ngra b ni r<sub>1</sub> ga bo`lib, bo`linmasini q<sub>1</sub>, qoldig’ini esa r<sub>2</sub> bilan belgilaylik. hamda ekanligi tabiiy. bo`lgani uchun . endi, r₁ ni r₂ ga bo`lib, larni topamiz. Demak, Bu jarayonni yetarlicha davom ettirish mumkin.

Ushbu jarayon ertami yoki kech albatta to`xtaydi, chunki barcha . musbat butun sonlar har хil va ularning har biri b dan kichik. Demak, bunday sonlarning miqdori b dan katta emas va jarayon ko`pi bilan 6 ta qadamdan keyin tugashi lozim. Jarayon faqat navbatdagi qoldiq nolga teng bo`lgan holdagina uzilib qolishi mumkin.

Tavsiflangan ushbu jarayon Evklid algoritmi deb ataladi. Uni qo`llash evaziga quyidagi tengliklar ketma-ketligini hosil qilamiz:

(2.3)

ketma-ketlikning noldan farqli oxirgi satrini ko`raylik. Aynan ana shu hadni sifatida qaraymiz. Hususan, bu sifatida b soni ham kelishi mumkin (umumiyliu uchun deb olish mumkin). sonining ga bo`linishi tabiiy. (2.3) dan oxiridan bitta avvalgi sonni olaylik. Uning o`ng tomonidagi har ikki qo`shiluvchi ga bo`linadi. Shuning uchun ham ga bo`linadi. Huddi shu usul bilan ishonch hosil qilish (qo`shiluvchi usuli bilan) mumkinki, ga sonlarining bari bo`linadi. Shunday qilib, soni a va b sonlari uchun eng katta umumiy bo`luvchi bo`lar ekan. Buning uchun a va b sonlarining ixtiyoriy umumiy bo`luvchisi ga bo`linishini isbotlash yetarli.

Faraz qilaylik, a va b sonlarining umumiy bo`luvchisi d bo`lsin. (2.3) ning birinchi tengligidan d ni ga bo`lib ko`ramiz. U holda (2.3) ning ikkinchi tengligidan d ni ga bo`lamiz. Xuddi shu zaylda (Qo`shiluvchi !) d ni larga bo`lish lozim.

Biz bu bilan Evklid algoritmini natural a va b sonlariga qo`llab, bu sonlarning eng katta umumiy bo`luvchisini hosil qilish mumkinligini isbotladik. Natural a va b sonlarining eng katta umumiy bo`luvchisini (a, b) ko`rinishida belgilaymiz.

Ma`lumki, a soni b soniga faqat va faqat (a. b)=b bo`lgandagina bo`linadi.

Misol uchun (a, b)= (6765, 610) ni topaylik:

Shunday qilib,

Ikkita Fibonachchi sonlarining eng katta umumiy bo`luvchisi yana Fibonachchi soni bo`lishi tasodif emas. Biz keyinchalik doimo shunday bo`lishini ko`rsatamiz.

5. Evklid algoritmiga o`xshash hodisa geometriyada ham uchraydi. Bu masala ikkita o`lchash mumkin bo`lgan kesmalarning umumiy o`lchamini topish jarayonidan iborat. Haqiqatdan ham, uzunliklari a va b (ab) bo`lgan ikkita kesmani qaraylik. Birinchi kesmadan ikkinchisini necha marta iloji bo`lsa, shuncha marta kesamiz. Agar b>a bo`lsa, biz bu ishni biror marta ham bajara olmaymiz. Oxirgi qoldiq kesmaning uzunligini orqali belgilaymiz. Bu xolda <b ekanligi ma`lum. endi b kesmadan ni necha marta iloji bo`lsa, shuncha marta ayiramiz. Oxirgi qoldiq kesmani bilan belgilaymiz. Bu ishni bir necha marta takrorlab, uzunliklari kamayib boradigan qoldik kesmalar ketma-ketligini hosil qilamiz. Shu yergacha jarayonning Evklid algoritmiga o`xshashligi ko`rinib turibdi.

Farq qiladigan jihati shu yerdaki, kesmalarni ayirishdagi qoldiq kesmalar ketma-ketligi uzilmasligi mumkin, natural sonlar uchun esa bunday emas.

6. Ikki sonning eng katta umumiy bo`luvchisi uchun bir nechta xossalarni aniqlaymiz.