Tub sonlar nazariyasi

1. Tub sonlar

   1. Tub sonlar nazariyasi.

1 dan farqli barcha natural sonlar tub va murakkab sonlarga bo’linadi. Bo’luvchilari faqat o’zi va bir bo’lgan natural sonlarga tub sonlar deyiladi. Boshqa natural sonlar murakkab sonlar deyiladi. Masalan, 2, 5, 37, 1979 – tub sonlar. 4, 25, 162, 2553 sonlar esa murakkab sonlar. Tub sonlar ham murakkab sonlar kabi cheksiz ko’pdir. Evklid tub sonlarga quyidgicha ta’rif bergan: «Tub sonlar faqat bir bilan o’lchanuvchidir, murakkab sonlar boshqa biror son bilan o’lchanuvchidir».
Har bir murakkab natural soni sodda ko’paytuvchilarga ajratish mumkin. Masalan, 2553 = 3*23*37. Tub sonlarni ular yordamida boshqa sonlar yasaladigan elementar g’ishtchalar deb ham atash mumkin. Arifmetikaning asosiy teoremasi quyidagicha ta’kidlanadi: agar ko’paytuvchilarning qatnashish tartibini inobatga olmaydigan bo’lsak, u holda berilgan natural sonning ikkita sodda ko’paytuvchilarga yoyilmasi bir xildir.
Berilgan natural sonning tubligini isbotlash uchun bu sonning ikkidan boshlab shu sonning kvadrat ildizigacha bo’lgan birorta ham songa bo’linmasligini isbotlash etarlidir. Agar u son shu oraliqdagi sonlarning birortasiga bo’linsa, u murakkab son bo’ladi.
Tub sonlarni ajratishning qulay usuli quyidagi kuzatuvga asoslanadi: agar natural sonlar ketma-ketligini qatorasiga yozib olsak, u holda, 2 sonidan keyingi har ikkinchi soni o’chirsak, biz 2 ga karrali barcha sonlarni ajratib olamiz, 3 sonidan keyingi har uchinchi soni o’chirsak, biz 3 ga karrali barcha sonlarni ajratib olamiz. Umuman, K qanday natural son bo’lmasin, K dan keyingi har K-sonni o’chirish bilan biz barcha K ga karrali sonlarni ajratib olamiz. Shuning uchun ham, agar bizga N dan oshmaydigan barcha tub sonlarni topish kerak bo’lsa, u holda 2 dan N gacha bo’lgan barcha natural sonlarni qatorasiga yozib chiqamiz. Birinchi tub son 2 ekanligini ta’kidlab o’tamiz. So’ngra «ajratish» usuliga asosan 2 ga karrali sonlarni o’chiramiz; birinchi o’chirilmagan son 3, u navbatdagi tub son. Barcha 3 ga karrali sonlarni o’chiramiz. Birinchi o’chirilmagan son 5, u navbatdagi tub son va hakozo. Bu jarayonni N dan katta bo’lgan tub songa etguncha davom ettiramiz. Barcha o’chirilmay qolgan sonlar tub sonlardir.
Tub sonlarni aniqlashning bunday usuli eramizdan oldingi III asrda yashagan grek matematigi Eratosfenga ham ma’lum edi. Eratosfenning davrida elim taxtachalarga yozishardi, sonlarni o’chirishning o’rniga esa taxtachalarning kerakli joyida teshishardi. Shuning uchun ham bu usul «Eratosfen reshetkasi» deyiladi.
Har xil davrlarda matematiklar unga kiruvchi o’zgaruvchilarning har xil qiymatlarida tub sonlarni beruvchi formulalarni izlashgan. Masalan, L.Eyler n = 0, 1, 2, … , 40 larda tub sonlarni beruvchi formula sifatida n² – n + 41 ko’phadni ko’rsatgan. Ammo o’zining barcha butun qiymatlarida tub sonlarni beruvchi bir o’zgaruvchili ko’phadning yo’qligini isbotlash oson.
P. Ferma (2*2)^K + 1 (K =0, 1, 2, 3, 4 lar uchun bu 3, 5, 17, 257, 65537 sonlari) ko’rinishdagi barcha sonlar tub degan taxminni ilgari surgan. Ammo L. Eyler bu taxminni rad etgan va K = 5 da bu Ferma soni tub ekanligini isbotlagan. Baribir o’zgaruvchilarning barcha butun qiymatlarida tub sonlarni beruvchi formulalar mavjud. Yu.V. Matisevich barcha tub sonlarni bir martadan beruvchi, ko’p o’zgaruvchili ko’phad mavjudligini, hamda uning barcha musbat qiymatlar tub son ekanligini isbotlagan.
Qadim zamonlardan matematiklarni tub sonlarning natural sonlar qatoridagi joylashishlari qiziqtirib kelgan. Evklidning natural sonlar qatoridagi tub sonlarning cheksizligini tasdiqlovchi mulohazasi Evklidning butun sonlarining eng katta umumiy bo’luvchisini topish algoritmiga asoslanadi. Ikkita butun musbat sonlarning eng katta umumiy bo’luvchisini topish uchun avval katta son kichigiga bo’linadi, so’ngra ikkinchi son birinchi bo’linmaning qoldig’iga bo’linadi va hakozo. Oxirgi noldan farqli musbat qoldiq berilgan sonlarning eng katta umumiy bo’luvchisi bo’ladi. Berilgan sonlarni a va b bilan, bo’lish natijasida hosil bo’lgan musbat qoldiqlarni r₁, r₂, . . . , r_n bilan, to’liqsiz bo’linmalarni esa q₁, q₂, . . . , q_n lar bilan belgilab Evklid algoritmini quyidagi ketma-ketlik ko’rinishda yozish mumkin
a = b*q₁ + r₁
b = r₁*q₂ + r₂
r₁= r₂*q₃ + r₃
. . . . . . . . . . .
r_n-2 = r_n-1*q_n + r_n
r_n-1 = r_n*q_n+1 .
Misol. a = 777 va b =629 sonlar berilgan bo’lsin. Ular uchun Evklid algoritmini yozib chiqsak quyidagi munosabatlarga ega bo’lamiz
777 = 1*629 + 148
629 = 148*4 + 37
147 = 37*4.
Bu ketma-ketlikda oxirgi noldan farqli qoldiq 37 ga teng va u 777 va 629 sonlari uchun eng katta umumiy bo’luvchi bo’ladi.
Evklid algoritmi ba’zi bir maxsus ko’rinishdagi, masalan, 4*n-1 ko’rinishdagi tub sonlar uchun, tub sonlarning soni cheksizligini isbotlashda ham qo’llanilishi mumkin. Ozgina o’zgartirishlardan so’ng bu mulohazani 4*n+1, 6*n+1 va boshqa ko’rinishdagi tub sonlarning cheksizligini isbotlash mumkin.

2.