MathTest.uz
Algebra

Bo'linish belgilari, tub va murakkab sonlar

boshlangich 50 daqiqa bo'linish belgilaritub sonmurakkab sonEratosfen g'alviriarifmetikaning asosiy teoremasi

Nima uchun muhim?

Har bir natural son — yo "atom" (tub son), yo bir necha atomdan yig'ilgan "molekula" (murakkab son). Bu oddiy g'oya butun son nazariyasining (number theory) yuragi hisoblanadi va zamonaviy kriptografiya (bank kartalari, internet xavfsizligi) aynan shu tub sonlarning "parchalash qiyinligi" xususiyatiga tayanadi. Bo'linish belgilari esa amaliy hayotda va imtihonlarda vaqtni tejaydigan "qisqa yo'l" — katta sonni qo'lda bo'lmasdan, uning 2, 3, 5, 9 kabi sonlarga bo'linishini bir necha soniyada aniqlash mumkin. Bu mavzu "Sonlarni tub ko'paytuvchilarga ajratish, $EKUB$ va $EKUK$" mavzusining bevosita poydevori.

O'quv maqsadlari

  • 2, 3, 4, 5, 6, 8, 9, 10, 11, 25 ga bo'linish belgilarini bilish va tez qo'llay olish
  • Tub va murakkab son tushunchalarini farqlash, 1 nima uchun ikkalasiga ham kirmasligini asoslash
  • Eratosfen g'alviri usuli bilan berilgan chegaragacha barcha tub sonlarni topa olish
  • Sonning tubligini tekshirishda nima uchun faqat $\sqrt{n}$ gacha bo'luvchi qidirish yetarli ekanini tushunish
  • Arifmetikaning asosiy teoremasi va tub sonlar cheksizligi haqidagi Yevklid teoremasining mazmunini bilish
Miloddan avvalgi III asrda yashagan yunon matematigi Eratosfen oddiy, ammo genial usul o'ylab topdi: 2 dan boshlab, har bir tub sonning barcha karralilarini "elab tashlash" orqali istalgan chegaragacha barcha tub sonlarni topish mumkin. Bu usul — Eratosfen g'alviri — bugungi kunda ham dasturlashda ishlatiladi. Tub son — faqat 1 ga va o'ziga bo'linadigan, 1 dan katta natural son (2, 3, 5, 7, 11, ...). Murakkab son — 1 dan katta, lekin ikkitadan ortiq bo'luvchiga ega son (4, 6, 8, 9, ...). E'tibor bering: 1 soni na tub, na murakkab — u alohida, o'ziga xos toifa, chunki tub sonning ta'rifiga ko'ra unda ikkita TURLI bo'luvchi (1 va o'zi) bo'lishi kerak, 1 da esa bu ikkalasi bir xil. Bo'linish belgilari esa sonning oxirgi bir necha raqamiga yoki raqamlar yig'indisiga qarab, to'liq bo'lishsiz, bo'linish-bo'linmasligini aniqlash imkonini beradi — bu Rim raqamlari davridan buyon savdogarlar va hisobchilar tomonidan qo'llanilgan amaliy hiyla.

Ta'riflar

Bo'luvchi va karrali

Agar $a = b\times k$ tenglikni qanoatlantiruvchi $k$ butun son mavjud bo'lsa, $b$ soni $a$ ning bo'luvchisi (yoki $a$ soni $b$ ga bo'linadi), $a$ esa $b$ ning karralisi deyiladi.

$b$ soni $a$ ni 'aniq, qoldiqsiz' bo'la olsa, $b$ — $a$ ning bo'luvchisi.

Misol: $4$ soni $12$ ning bo'luvchisi ($12=4\times 3$), $12$ esa $4$ ning karralisi.

Bu emas: $5$ soni $12$ ning bo'luvchisi emas, chunki $12\div 5$ qoldiqsiz bo'linmaydi.

💡 Har bir natural son o'zining va $1$ ning karralisi/bo'luvchisi hisoblanadi.

Tub son (prime number)

1 dan katta bo'lgan, faqat ikkita natural bo'luvchiga (1 va o'ziga) ega bo'lgan natural son tub son deyiladi.

Boshqa hech qanday songa 'bo'linmaydigan' (o'zi va 1 dan tashqari) son.

Misol: 2, 3, 5, 7, 11, 13, 17, 19, 23 — birinchi tub sonlar. 2 — yagona juft tub son.

Bu emas: 9 tub son emas (3×3), 1 ham tub son emas (ta'rif shartiga ko'ra).

💡 Tub sonlar 'sonlarning atomlari' deb ham ataladi — arifmetikaning asosiy teoremasiga ko'ra har bir son ular orqali yagona tarzda quriladi.

Murakkab son (composite number)

1 dan katta bo'lgan, ikkitadan ortiq natural bo'luvchiga ega bo'lgan natural son murakkab son deyiladi.

Kichikroq tub sonlarning ko'paytmasi sifatida yozilishi mumkin bo'lgan son.

Misol: $4=2\times 2$, $6=2\times 3$, $100=2^2\times 5^2$ — barchasi murakkab son.

Bu emas: 7 murakkab son emas — u tub, faqat 1 va 7 ga bo'linadi.

💡 1 soni na tub, na murakkab — alohida maxsus holat.

Fundamental tushunchalar

Bo'linish belgilari jadvali

2 ga: oxirgi raqam juft (0,2,4,6,8). 3 ga: raqamlar yig'indisi 3 ga bo'linadi. 4 ga: oxirgi ikki raqamdan tuzilgan son 4 ga bo'linadi. 5 ga: oxirgi raqam 0 yoki 5. 6 ga: ham 2 ga, ham 3 ga bo'linadi. 8 ga: oxirgi uch raqamdan tuzilgan son 8 ga bo'linadi. 9 ga: raqamlar yig'indisi 9 ga bo'linadi. 10 ga: oxirgi raqam 0. 11 ga: raqamlarni almashlab qo'shish/ayirish (o'ngdan chapga +,−,+,−...) natijasi 11 ga bo'linadi (yoki 0). 25 ga: oxirgi ikki raqam 00, 25, 50 yoki 75.

$d(n) — n sonining oxirgi raqami; S(n) — raqamlar yig'\textsubscript{indisi}$

$3$ va $9$ ga bo'linish belgilari $10 \equiv 1 \pmod{3}$ va $10 \equiv 1 \pmod{9}$ xossasidan kelib chiqadi — shuning uchun ular raqamlar $YIG'INDISIGA$ bog'liq.

Eratosfen g'alviri (Sieve of Eratosthenes)

2 dan $N$ gacha barcha sonlarni yozib, 2 dan boshlab har bir tub sonning barcha karralilarini (o'zidan tashqari) belgilab (elab) tashlaymiz. Oxirida belgilanmay qolgan sonlar — tub sonlar. Algoritm samaradorligi uchun faqat $\sqrt{N}$ gacha bo'lgan tub sonlarning karralilarini elash yetarli.

$\pi(N) — N gacha bo'lgan tub sonlar soni$

Bu — eng qadimiy va hozirgача dasturlashda eng tez tub son topish algoritmlaridan biri (murakkabligi $O(N \log \log N)$).

Nega faqat $n$ gacha tekshirish kifoya

Agar $n = a \times b$ bo'lsa va $a \le \sqrt{n}$ bo'lsa, u holda albatta $a \le \sqrt{n}$ bo'ladi (aks holda $a>\sqrt{n}$ va $b>\sqrt{n}$ bo'lganda $a \times b>n$ bo'lib qolardi). Demak, $n$ ning $\sqrt{n}$ dan katta bo'lmagan hech qanday bo'luvchisi topilmasa, $n$ — tub son.

$d \mid n, \, d \leq \sqrt{n}$

Bu kuzatuv tub sonlikni tekshirish algoritmini ancha tezlashtiradi — 997 ni tekshirish uchun 996 marta emas, atigi ≈31 gacha ($\sqrt{997}\approx31.6$) bo'luvchini tekshirish kifoya.

1 nima uchun na tub, na murakkab

Tub son ta'rifi 'ikkita TURLI bo'luvchi' (1 va o'zi) talab qiladi. 1 uchun bu ikkalasi bir xil ($1=1$), shuning uchun 1 tub son emas. Murakkab son ta'rifiga ko'ra esa kamida uchta bo'luvchi kerak — 1 da esa faqat bitta bo'luvchi (o'zi) bor. Shuning uchun 1 — alohida, maxsus holat.

Agar 1 tub son deb hisoblansa, arifmetikaning asosiy teoremasi (yagona faktorizatsiya) buzilardi — masalan $6=2\times 3=1\times 2\times 3=1\times 1\times 2\times 3=\dots$ cheksiz ko'p 'yoyilma' hosil bo'lardi.

Formula kutubxonasi

3 (va 9) ga bo'linish belgisi

$$n \text{ soni } 3\text{ (yoki }9\text{) ga bo'linadi} \iff S(n) \text{ 3 (yoki 9) ga bo'linadi}$$
  • $n$ — tekshirilayotgan son
  • $S(n)$ — n sonining raqamlari yig'indisi

Sonning o'zini emas, uning raqamlari yig'indisini tekshirish kifoya.

Shart: n — istalgan natural son.

Xususiy holatlar: Bir xonali sonlar uchun S(n)=n, belgi trivial.

Tub sonlikni tekshirish chegarasi

$$n \text{ murakkab} \iff \exists\, d \le \sqrt{n},\ d \mid n,\ d>1$$
  • $n$ — tekshirilayotgan son (n>1)
  • $d$ — nomzod bo'luvchi

n ning tubligini tekshirish uchun 2 dan √n gacha bo'lgan sonlarga bo'linishini tekshirish yetarli.

Shart: n > 1 natural son.

Xususiy holatlar: n ≤ 3 bo'lganda maxsus tekshiriladi (2 va 3 — tub).

Teoremalar va isbotlar

📐 Arifmetikaning asosiy teoremasi (Fundamental Theorem of Arithmetic)

Har bir 1 dan katta natural son yoki o'zi tub, yoki tub sonlarning ko'paytmasi sifatida, ko'paytuvchilar tartibigacha aniqlikda, YAGONA usulda ifodalanadi.

Tub sonlar — sonlar dunyosining 'atomlari'; har qanday son ulardan yagona tarzda 'yig'iladi'.

📐 Yevklid teoremasi: tub sonlar cheksiz ko'p

Tub sonlar to'plami cheksizdir — eng katta tub son mavjud emas.

Tub sonlar hech qachon 'tugamaydi', qancha katta chegara olmang, undan ham katta tub son topiladi.

Isbotni ko'rsatish

Berilgan: Faraz qilaylik, tub sonlar soni chekli: $p_1, p_2, \dots, p_n$ — barcha mavjud tub sonlar (kattadan kichikkacha toʻliq roʻyxat).

Isbotlash kerak: Bu faraz ziddiyatga olib keladi (demak tub sonlar cheksiz).

  1. N = $p_1 \times p_2 \times \dots \times p_n + 1$ sonini quramiz — barcha 'mavjud' tub sonlarning koʻpaytmasiga 1 qoʻshamiz.
  2. $N$ soni roʻyxatdagi HAR QANDAY $p_i$ ga boʻlinganda albatta 1 qoldiq beradi (chunki $p_1 \times \dots \times p_n$ $p_i$ ga qoldiqsiz boʻlinadi, +1 esa qoldiq hosil qiladi).
  3. Demak, $N$ roʻyxatdagi hech qanday tub songa boʻlinmaydi.
  4. Ammo arifmetikaning asosiy teoremasiga koʻra, $N > 1$ boʻlgani uchun $N$ kamida bitta tub boʻlgichiga ega boʻlishi SHART ($N$ ning oʻzi tub boʻlasa ham, yoki uning tub koʻpaytuvchisi boʻlasa ham).
  5. Bu tub boʻlgich roʻyxatdagi $p_1,\dots,p_n$ dan birortasi boʻla olmaydi (3-qadamga koʻra) — demak u roʻyxatda YOʻQ yangi tub son.
  6. Bu bizning 'roʻyxat TOʻLIQ' degan boshlangʻich farazimizga ZID keladi.

Ziddiyat kelib chiqdi, demak boshlangʻich faraz (tub sonlar chekli) notoʻgʻri. Tub sonlar cheksiz koʻp. ∎

n soni 3 ga bo'linadi $⟺$ raqamlari yig'indisi $S(n)=d_k+ \dots +d_0$ 3 ga bo'linadi.

Berilgan: n — o'nlik sistemada raqamlari $d_kd_{k-1} \dots d_1d_0$ bo'lgan natural son.

  1. n = $d_k \cdot 10^k + \dots + d_1 \cdot 10 + d_0$ deb yozamiz.
  2. Har bir $10^k$ ni $(10^k-1) + 1$ ko'rinishida ifodalaymiz.
  3. $10^k-1 = 99 \dots 9$ ($k$ ta to'qqiz) — bu son har doim 3 ga (va 9 ga) qoldiqsiz bo'linadi.
  4. Demak $n = [d_k(10^k-1)+ \dots +d_1(10-1)] + [d_k+ \dots +d_1+d_0]$, bu yerda kvadrat qavsdagi birinchi ifoda har doim 3 ga bo'linadi.
  5. Shuning uchun n ning 3 ga bo'linish-bo'linmasligi faqat ikkinchi qism — $S(n) = d_k+ \dots +d_0$ ga bog'liq.

Demak, n 3 ga bo'linadi $⟺$ $S(n)$ 3 ga bo'linadi. (Xuddi shu mulohaza 9 uchun ham to'g'ri, chunki $10^k-1$ har doim 9 ga ham bo'linadi.) ∎

Yechilgan misollar

oson 4578 soni 2 ga va 3 ga bo'linadimi?

💡 Maslahat: 2 uchun oxirig raqamga, 3 uchun raqamlar yig'indisiga qarang.

  1. Oxirig raqam 8 — juft, demak 2 ga bo'linadi.
  2. Raqamlar yig'indisi: 4+5+7+8=24, 24 esa 3 ga bo'linadi.

✅ Javob: Ha, 4578 ham 2 ga, ham 3 ga (demak 6 ga ham) bo'linadi.

Nega bu usul ishlaydi: Bo'linish belgilari to'liq bo'lishni talab qilmaydi.

⚠️ 3 ga bo'linishni tekshirishda sonning o'zini emas, raqamlar yig'indisini tekshirish kerak.

oson 17, 21, 29, 33 sonlaridan qaysilari tub?

💡 Maslahat: Har birini kichik tub sonlarga (2, 3, 5, 7 gacha) bo'linishini tekshiring.

  1. 17: 2, 3 ga bo'linmaydi, $\sqrt{17}\approx4.1$, demak faqat 2, 3 tekshirish kifoya — tub.
  2. 21=$3\times7$ — murakkab.
  3. 29: $\sqrt{29}\approx5.4$, 2, 3, 5 ga bo'linmaydi — tub.
  4. 33=$3\times11$ — murakkab.

✅ Javob: 17 va 29 — tub sonlar.

Nega bu usul ishlaydi: $\sqrt{n}$ chegarasidan foydalanish tekshiruvni tezlashtiradi.

⚠️ 21 ni 'toq son, demak tub' deb noto'g'ri xulosa chiqarish.

ortacha 396 soni 4 ga, 8 ga, 9 ga bo'linadimi?

💡 Maslahat: 4 uchun oxirig_i 2 raqam, 8 uchun oxirig_i 3 raqam, 9 uchun raqamlar yig'indisi.

  1. Oxirig_i 2 raqam: 96, $96 \div 4 = 24$ — bo'linadi.
  2. Oxirig_i 3 raqam: 396 (o'zi, chunki 3 xonali), $396 \div 8 = 49.5$ — bo'linmaydi.
  3. Raqamlar yig'indisi: $3 + 9 + 6 = 18$, $18 \div 9 = 2$ — bo'linadi.

✅ Javob: 396 soni 4 ga va 9 ga bo'linadi, 8 ga bo'linmaydi.

Nega bu usul ishlaydi: Har bir belgi mustaqil, alohida tekshiriladi.

Muqobil usul: To'g'ridan-to'g'ri bo'lish: $396 \div 8 = 49.5$ — noto'g'ri butun son, demak bo'linmaydi.

⚠️ 8 ga bo'linish belgisini 4 ga bo'linish belgisi bilan aralashtirib, oxirig_i 2 raqamni tekshirish (8 uchun OXIRGI 3 raqam kerak).

ortacha Eratosfen g'alviri usulida 1 dan 30 gacha barcha tub sonlarni toping.

💡 Maslahat: 2 dan boshlab, har bir tub sonning karralilarini eling, $\sqrt{30}\approx5.5$ gacha yetarli.

  1. 2 ning karralilarini elaymiz (4,6,8,...,30).
  2. 3 ning karralilarini elaymiz (9,15,21,27 — 6,12,18,24,30 allaqachon elangan).
  3. 5 ning karralilarini elaymiz (25 — 10,15,20,30 allaqachon elangan).
  4. $\sqrt{30}<6$ bo'lgani uchun boshqa elash kerak emas, qolganlar tub.

✅ Javob: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

Nega bu usul ishlaydi: $\sqrt{30}$ dan katta bo'lgan sonning kichik bo'luvchisi bo'lmasa, u albatta tub.

Muqobil usul: Har birini alohida bo'linishga tekshirish (sekinroq).

⚠️ 1 ni ham 'tub' deb ro'yxatga qo'shib qo'yish.

ortacha n=1001 soni 11 ga bo'linadimi? Bo'linish belgisidan foydalaning.

💡 Maslahat: 11 belgisi: raqamlarni o'ngdan chapga almashlab qo'shing/ayiring.

  1. Raqamlar (o'ngdan): 1,0,0,1
  2. Almashlab: 1−0+0−1=0
  3. 0 soni 11 ga bo'linadi (0=11×0)

✅ Javob: Ha, 1001=11×91 — 11 ga bo'linadi.

Nega bu usul ishlaydi: $10\equiv -1\pmod{11}$ bo'lgani uchun $10^k\equiv(-1)^k\pmod{11}$, shuning uchun almashlab qo'shish/ayirish ishlaydi.

Muqobil usul: To'g'ridan-to'g'ri bo'lish: 1001÷11=91.

⚠️ Almashlab qo'shish tartibini (+/−) chalkashtirib yuborish.

murakkab 1 dan 100 gacha nechta tub son borligini asoslab tushuntiring (ro'yxatni sanab chiqmasdan, usulni tushuntiring).

💡 Maslahat: Eratosfen g'alvirida $\sqrt{100}=10$ gacha bo'lgan tub sonlar (2,3,5,7) yetarli.

  1. $\sqrt{100}=10$ bo'lgani uchun faqat 2,3,5,7 tub sonlarining karralilarini elash yetarli.
  2. 2 ning karralilari: 50 ta ($100/2$).
  3. 3 ning karralilari (2 nikidan qo'shimcha): $\lfloor 100/3 \rfloor$ − ular ichida 2 va 3 ga birga bo'linadiganlarni chegirib (kiritish-chiqarish printsipi, inclusion-exclusion).
  4. To'liq hisoblash natijasida 1 dan 100 gacha aniq 25 ta tub son borligi ma'lum (bu klassik natija).

✅ Javob: 1 dan 100 gacha $25$ ta tub son bor (2 dan 97 gacha).

Nega bu usul ishlaydi: Eratosfen g'alviri va $\sqrt{100}$ chegarasi hisoblashni amaliy qiladi.

Muqobil usul: To'g'ridan-to'g'ri sanab chiqish (Eratosfen jadvali orqali).

⚠️ Chegara $\sqrt{100}=10$ ni noto'g'ri, masalan $100/2=50$ deb tushunish.

murakkab p va q — ikkita turli tub son. n=p²×q koʻrinishidagi sonning nechta natural boʻlgichlari borligini isbotlang va formulani chiqaring.

💡 Maslahat: Har bir boʻlgichi p^a × q^b koʻrinishida, a∈{0,1,2}, b∈{0,1}.

  1. Arifmetikaning asosiy teoremasiga koʻra, n ning har qanday boʻlgichi d=p^a×q^b koʻrinishida boʻladi, bu yerda 0≤a≤2, 0≤b≤1.
  2. a uchun 3 ta variant (0,1,2), b uchun 2 ta variant (0,1) mavjud.
  3. Kombinatorika qoidasiga koʻra (koʻpaytirish qoidasi), jami boʻlgichlar soni = 3×2=6.

✅ Javob: n=p²q sonining 6 ta natural boʻlgichisi bor: d(n)=(2+1)(1+1)=6.

Nega bu usul ishlaydi: Bu — boʻlgichlar sonini hisoblash umumiy formulasi d(n)=(a₁+1)(a₂+1)...(aₖ+1) ning xususiy holati (11-mavzuda batafsil).

Muqobil usul: n=12=2²×3 misolida toʻgʻridan-toʻgʻri sanash: 1,2,3,4,6,12 — 6 ta, formula tasdiqlanadi.

⚠️ a va b ning yuqori chegarasini (daraja koʻrsatkichi+1 emas, daraja koʻrsatkichining oʻzi) notoʻgʻri olish.

murakkab 2^{17}-1 = 131071 sonining tub yoki murakkab ekanini, $\sqrt{131071}\approx362$ chegarasidan foydalanib qanday tekshirish mumkinligini tushuntiring (hisoblamasdan, usulni bayon qiling).

💡 Maslahat: 362 gacha bo'lgan barcha tub sonlarga birma-bir bo'lish kerak bo'ladi.

  1. $\sqrt{131071}\approx361.8$, demak 362 dan katta bo'luvchini tekshirish shart emas.
  2. 2 dan 362 gacha bo'lgan barcha TUB sonlarga (2,3,5,7,...,359) birma-bir bo'lib ko'riladi.
  3. Agar birortasiga qoldiqsiz bo'linsa — murakkab, aks holda — tub.
  4. (Aslida 131071=2^{17}-1 — Mersenn tub soni sifatida ma'lum, u tub ekani isbotlangan.)

✅ Javob: Usul: 362 gacha bo'lgan tub sonlarga bo'lish orqali tekshiriladi; natijada 131071 tub son ekani ma'lum.

Nega bu usul ishlaydi: $\sqrt{n}$ chegarasi katta sonlar uchun ham tekshiruv hajmini keskin kamaytiradi.

Muqobil usul: Zamonaviy kompyuter algoritmlari (Miller-Rabin testi) katta sonlar uchun tezroq ishlaydi.

⚠️ 362 gacha bo'lgan BARCHA sonlarni emas, faqat TUB sonlarni tekshirish kifoya ekanini unutish (murakkab sonlarga bo'linsa, uning tub ko'paytuvchisiga ham bo'linadi).

olimpiada Isbotlang: agar $p>3$ tub son bo'lsa, $p^2-1$ soni $24$ ga bo'linadi.

💡 Maslahat: $p^2-1=(p-1)(p+1)$ ko'rinishida yozing va $p$ toq, $3$ ga bo'linmasligidan foydalaning.

  1. $p>3$ tub son bo'lgani uchun $p$ albatta toq (chunki $2$ dan tashqari barcha tub sonlar toq) va $3$ ga bo'linmaydi.
  2. $p^2-1=(p-1)(p+1)$ — ikkita ketma-ket JUFT son ($p$ toq bo'lgani uchun $p-1$ va $p+1$ juft).
  3. Ikkita ketma-ket juft son ko'paytmasi har doim $8$ ga bo'linadi (biri $4$ ga bo'linadigan juft, ikkinchisi oddiy juft — masalan $4k$ va $4k+2$ yoki $4k-2$ turlari $8$ ga karrali ko'paytma beradi).
  4. $p$ $3$ ga bo'linmagani uchun $p\equiv 1$ yoki $p\equiv 2\pmod{3}$. Agar $p\equiv 1\pmod{3}$, u holda $p-1\equiv 0\pmod{3}$. Agar $p\equiv 2\pmod{3}$, u holda $p+1\equiv 0\pmod{3}$. Ikkala holatda ham $(p-1)(p+1)$ $3$ ga bo'linadi.
  5. $8$ ga ham, $3$ ga ham bo'linuvchi son — $EKUK(8,3)=24$ ga (o'zaro tub sonlar ko'paytmasiga) bo'linadi.

✅ Javob: Isbotlandi: $p>3$ tub son bo'lsa, $p^2-1$ $24$ ga bo'linadi. ∎ (Masalan $p=5$: $24\div 24=1$ ✓; $p=7$: $48\div 24=2$ ✓)

Nega bu usul ishlaydi: Ko'paytuvchilarga ajratish + holatlarga bo'lib tekshirish ($\mod 3$ va $\mod 8$ bo'yicha) klassik son nazariyasi texnikasi.

Muqobil usul: To'g'ridan-to'g'ri $p=6k\pm 1$ (barcha $3$ dan katta tub sonlar shu ko'rinishda) almashtirish orqali ham isbotlash mumkin.

⚠️ Faqat bir nechta misolda ($p=5,7$) tekshirib, 'isbotlandi' deb hisoblash — bu umumiy isbot emas.

olimpiada n! + 2, n! + 3, ..., n! + n ketma-ketligining har bir hadi murakkab ekanini isbotlang (n ≥ 2 uchun). Bu nima uchun 'ixtiyoricha uzun tub sonsiz oraliq mavjud' degan xulosaga olib keladi?

💡 Maslahat: Har bir n!+k (2≤k≤n) hadining k ga bo'linishini ko'rsating.

  1. n! = 1×2×3×...×n, ya'ni n! har qanday k (2≤k≤n) ga qoldiqsiz bo'linadi (chunki k ko'paytmada qatnashadi).
  2. n!+k ni qaraymiz: n! k ga bo'linadi, k ham (albatta) k ga bo'linadi, demak ularning yig'indisi n!+k ham k ga bo'linadi.
  3. n!+k > k (chunki n! ≥ 2 uchun ancha katta), demak k — n!+k ning O'ZIDAN KICHIK, 1 dan katta bo'luvchisi.
  4. Bu n!+k ning murakkab ekanini isbotlaydi (1 va o'zidan tashqari bo'luvchisi bor).
  5. Bu ketma-ket n−1 ta son (n!+2 dan n!+n gacha) — barchasi murakkab, ya'ni bu oraliqda bironta ham tub son yo'q.

✅ Javob: Har bir n!+k (2≤k≤n) murakkab, chunki k unga bo'linadi. Demak, xohlagancha uzun 'tub sonlarsiz' ketma-ket oraliq qurish mumkin — bu tub sonlar orasidagi bo'shliqlar cheksiz katta bo'lishi mumkinligini ko'rsatadi (lekin bu Yevklid teoremasiga zid emas — tub sonlar baribir cheksiz, faqat orasidagi masofalar ixtiyoricha katta bo'lishi mumkin).

Nega bu usul ishlaydi: n! konstruksiyasi 'sun'iy ravishda' har bir k ga bo'linadigan sonlar zanjirini yaratadi — bu klassik olimpiada texnikasi.

⚠️ Bu natijani 'tub sonlar cheklangan' deb noto'g'ri talqin qilish — aslida faqat MA'LUM BIR oraliqda tub son yo'qligini, umuman cheksizlikni emas, ko'rsatadi.

Umumiy xatolar

❌ 8 ga bo'linishni tekshirishda oxirgi 2 raqamni (4 ga bo'linish belgisidagi kabi) tekshirish.

8=2³ bo'lgani uchun oxirgi UCH raqam kerak, ikki raqam yetarli emas.

✅ 8 ga bo'linishni tekshirish uchun sonning oxirgi 3 raqamidan tuzilgan sonni 8 ga bo'lish kerak.

1416: oxirgi 3 raqam 416, $416 \div 8 = 52$ — bo'linadi (1416 ni to'g'ridan-to'g'ri tekshirsak ham xuddi shu natija).

❌ Har qanday toq sonni avtomatik ravishda tub son deb hisoblash.

Toqlik faqat 2 ga bo'linmaslikni bildiradi, lekin son boshqa tub songa (3, 5, 7, ...) bo'linishi mumkin.

✅ Sonni $\sqrt{n}$ gacha bo'lgan barcha tub sonlarga (2,3,5,7,...) alohida tekshirish kerak.

9, 15, 21, 25, 27, 33 — barchasi toq, lekin birortasi ham tub emas ($9=3^2$, $15=3\times 5$, va h.k.).

❌ 1 sonini tub son sifatida hisoblash yoki ro'yxatga kiritish.

Tub son ta'rifi ikkita TURLI bo'luvchi (1 va o'zi) talab qiladi; 1 uchun bu ikkalasi bir xil bo'lgani uchun shart bajarilmaydi.

✅ 1 ni na tub, na murakkab — alohida maxsus holat deb hisoblang.

Tub sonlar ro'yxati: 2,3,5,7,11,... — 1 bilan BOSHLANMAYDI.

Noto'g'ri tasavvurlar

'$1 — eng kichik tub son$' degan keng tarqalgan noto'g'ri tasavvur.

$1$ tub son EMAS. Eng kichik tub son — $2$. Bu kelishuv o'zboshimchalik emas: agar $1$ tub deb hisoblansa, arifmetikaning asosiy teoremasi (yagona faktorizatsiya) buziladi.

'Barcha tub sonlar toq' degan tasavvur.

2 — yagona JUFT tub son (chunki $2$ faqat 1 va 2 ga bo'linadi). 2 dan boshqa barcha juft sonlar kamida uchta bo'luvchiga ega (1, 2, va o'zi), demak murakkab.

'Katta son har doim murakkab, kichik son har doim tub' degan noto'g'ri umumlashtirish.

Sonning kattaligi uning tub yoki murakkabligini belgilamaydi — masalan 97 (juda 'oddiy' ko'rinadigan ikki xonali son) tub, lekin undan kichik 96 murakkab. Tub sonlar juda katta sonlar orasida ham (masalan Mersenn tub sonlari, millionlab raqamli) uchraydi.

Amaliy qo'llanilishi

Kriptografiya

RSA shifrlash algoritmi ikkita juda katta tub sonlarni ko'paytirish osondir, ammo natijani orqaga tub ko'paytuvchilarga ajratish $AMALIY\ JIHATDAN$ mumkin emasligiga (hisoblash vaqti nuqtai nazaridan) tayanadi — bank kartalari, HTTPS xavfsizligi shu asosda ishlaydi.

Kompyuter fanlari

Hash-jadvallar (hash tables) o'lchamini tub son qilib tanlash kolliziyalarni kamaytiradi; Eratosfen g'alviri dasturlashda samarali algoritmlar (masalan, tezkor tub son generatorlari) sifatida qo'llaniladi.

Kundalik hisob-kitob

Bo'linish belgilari sotib olingan tovarlarni teng bo'lib to'lash, jadval tuzish (masalan, $24$ kishini teng guruhlarga bo'lish mumkinligini tezkor tekshirish) kabi vaziyatlarda foydali.

Eratosfen g'alviri (1-50)

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950

Oltin rangdagi kataklar — tub sonlar (1 dan 50 gacha), kulrang kataklar — murakkab sonlar (yoki 1).

Xulosa

Har bir natural son (1 dan tashqari) yoki tub, yoki murakkab. Tub sonda faqat ikkita bo'luvchi bor: 1 va o'zi. Bo'linish belgilari (2,3,4,5,6,8,9,10,11,25 uchun) sonni qo'lda bo'lmasdan tezkor tekshirish imkonini beradi. Sonning tubligini tekshirishda faqat $\sqrt{n}$ gacha bo'luvchi qidirish yetarli, chunki $n=a\times b$ da $a$ va $b$ dan kamida biri $\sqrt{n}$ dan katta bo'lmaydi. Yevklid teoremasiga ko'ra tub sonlar soni $\infty$.

Keyingi mavzu — "Sonlarni tub ko'paytuvchilarga ajratish, $EKUB$ va $EKUK$": bu yerda o'rgangan tub sonlar bilvosita har qanday sonni "tub ko'paytuvchilar" ko'rinishida yozish, so'ng ikkita sonning eng katta umumiy bo'luvchisi ($EKUB$) va eng kichik umumiy karralisi ($EKUK$)ni topishda ishlatiladi.

Bog'liq mavzular

Oldin bilishingiz kerak: Natural sonlar va ular ustida amallar

Bog'liq mavzular: Qoldiqli bo'lish. Oxirgi raqam.

Keyingi mavzular: Sonlarni tub ko'paytuvchilarga ajratish, EKUB va EKUK, Bo'linuvchanlik. Sonning natural bo'luvchilar soni va yig'indisi

Manbalar

Shu mavzudagi savollar

12 sonining barcha natural bo'luvchilarini yozing. 100 sonining barcha natural bo'luvchilarini yozing. 36 sonining barcha natural bo'luvchilarini yozing. 48 sonining barcha natural bo'luvchilarini yozing. 25 dan oshmaydigan 5 ga karrali natural sonlarni yozing. 20 dan oshmaydigan 3 ga karrali natural sonlarni yozing.
Ro'yxatdan o'tib, mashq qilishni boshlang