1-ma’ruza: Butun sonlar va kombinatorika. Qoldiqli va qoldiqsiz bo’lish

1-ma’ruza: Butun sonlar va kombinatorika.Qoldiqli va qoldiqsiz bo’lish.

Ma’lumki natural sonlar bu tabiiy (tabiat) sonlaridir. Bu so’z inglizcha natural so’zidan olingan bo’lib , o’zbek tilida tabiiy degan ma’noni bildiradi. Bu tabiiy sonlar ya’ni sonoqda ishlatiladigan sonlarni 1, tub sonlar va murakkab sonlarga ajratib o’rganish bizga natural sonlarni ya’nada yaxshiroq tushunishimizga yordam beradi. Har qanday N natural sonni quyidagicha yozish mumkin:

N = a_nqⁿ + a_n-1q^n-1 +……+ a₁q+ a₀ (1)
bunda 0 (i = 1,2,……,n) shart o’rinli bo’ladi.
Bu yuqoridagi (1) formula N natural sonni q asosli sanoq sistemasida yozish deb nomlaymiz va qisqacha ko’rinishi N_(q) deb belgilaymiz .
Bunga misol tariqasida ikkilik, sakkizlik va o’nlik `sanoq sistemasida (1) formula quyidagicha:
Ikkilik sanoq sistemasida
N=N₍₂₎ = a_n2ⁿ + a_n-12^n-1 +……+ a₁2+ a₀
bunda 0 (i = 1,2,……,n) shart o’rinli bo’ladi.
Sakkizlik sanoq sistemasida yuqoridagi(1) formula quyidagicha:
N=N₍₈₎ = a_n8ⁿ + a_n-18^n-1 +……+ a₁2+ a₀
bunda 0 (i = 1,2,……,n) shart o’rinli bo’ladi
Sakkizlik sanoq sistemasida yuqoridagi(1) formula quyidagicha:
N=N₍₁₀₎ = a_n10ⁿ + a_n-110^n-1 +……+ a₁10+ a₀ (2)
bunda 0 (i = 1,2,……,n) shart o’rinli bo’ladi.
1.Agar a-b va b-c sonlari m soniga qoldiqsiz bo’linsa, a-c soni ham m soniga qoldiqsiz bo’linadi.
2.Agar a-b va c-d sonlari m soniga qoldiqsiz bo’linsa, a+c- (b+d) soni ham m soniga qoldiqsiz bo’linadi.
3.Agar a-b soni m soniga qoldiqsiz bo’linsa, aⁿ-bⁿ soni ham m soniga qoldiqsiz bo’linadi.
4.Agar a-b soni m soniga qoldiqsiz bo’linsa, ak-bk soni ham mk soniga qoldiqsiz bo’linadi.
5.aⁿ-bⁿ soni a – b soniga qoldiqsiz bo’linadi.
6.a^2n-1+b^2n-1 soni a+b soniga qoldiqsiz bo’linadi.
7. a²ⁿ – b²ⁿ soni a+b soniga qoldiqsiz bo’linadi.
8.(a+b)ⁿ sonini a soniga bo’lgandagi qoldiq bⁿ sonini a soniga bo’lgandagi qoldiqqa tengdir.
Misol: 10ⁱ sonini 9 ga bo’lgandagi qoldiqni aniqlang.
Yechimi: 10ⁱ = (9+1)ⁱ ko’rinishida yozib olamiz.
Yuqoridagi 8-teorema yordamida (9+1)ⁱ sonini 9 ga bo’lganda qoldiq 1ⁱ sonini 9 ga bo’lgandagi qoldiqqa tengdir yani o’nning har qanday darajasini 9 ga bo’lganda qoldiq 1 ga teng bo’lar ekan.
Bu yuqoridagi teoremalarni o’zingiz isbotlashga harakat qiling.
Sizga ajoyib quyidagi Paskal aniqlagan natural sonlarning umumiy bo’linish alomatlarini aniqlab beruvchi formulasini tanishtirib o’tamiz.
N natural sonni ixtiyoriy m natural songa bo’linish alomatini aniqlaymiz.O’nlik sanoq sistemasida N natural soni quyidagicha yozilgan N = va r_i – 10ⁱ sonini m natural songa bo’lganda qoldiq bo’lsin. U holda a_nr_n + a_n-1r_{n-1 + …….+} a₁r₁ + a₀ son m natural songa bo’linsa, N natural son ham m natural songa bo’linadi.
Misol: Bu yuqoridagi Paskalning aniqlagan umumiy bo’linish alomati yordamida natural sonning 9 ga bo’linish alomatini aniqlaymiz.
Yechimi: Ixtiyoriy natural N sonni quyidagi ko’rinishda yozish mumkin.
N= = a_n10ⁿ + a_n-110^n-1+…..+a₁10+a₀
Sizga ma’lumki 10ⁱ sonini 9 ga bo’lganda qoldiq 1 bo’lishini yuqorida aniqlagan edik. Buning yordamida va Paskal qoidasiga asosan N natural son 9 ga qoldiqsiz bo’linishi uchun a_n+a_n-1+a_n-2 +…+a₁+a₀ son 9 ga qoldiqsiz bo’linishi kerak. Buni boshqacha qilib aytganda N natural sonning raqamlari yig’indisi 9 ga bo’linsa, shu natural sonning o’zi ham 9 ga qoldiqsiz bo’linadi.
Tub sonlar bu cheksiz natural sonlar ichida qanday qonuniyat bilan taqsimlanganini hali hech kim aniqlay olmagan. Lekin ba’zi tub sonlarni quyidagicha qonuniyat bilan yozish mumkin.
p = 4k+1 va p = 6k+5
Buni misollarda o’zingiz sinab ko’ring.
Agar siz berilgan N natural sonni murakkab yoki tub son ekanligini aniqlashiz uchun bu sonni dan kichik bo’lgan barcha tub sonlarga bo’lib ko’rishingiz kerak. Agar hech qaysi tub songa bo’linmasa, unda bu natural son tub son bo’ladi.
Har qanday murakkab sonni tub ko’paytuvchilarga ajratish mumkin. Uning umumiy ko’rinishi (kanonik yoyilmasi ) quyidagicha bo’ladi.
n = (bunda p₁, p₂ …….p_k – tub sonlardir). (3)
Bu n natural sonning natural bo’luvchilari soni quyidagicha topiladi.

Agar sizda n natural sonini tub ko’paytuvchilarga ajratilgan holati ma’lum bo’lsa, siz sonini natural bo’luvchilari sonini quyidagicha aniqlashiz ham mumkin.

N natural sonining natural bo’luvchilari yig’indisini topish uchun bu sonni eng avvalo tub ko’paytuvchilarga ajratish kerak ya’ni yuqoridaga (3) orqali ko’rinishda keltirish kerak.
S(n) =
N natural sonining barcha natural bo’luvchilari ko’paytmasi quyidagicha topiladi.
P(n) =

1 dan n gacha bo’lgan natural sonlar ichida n soni bilan o’zaro tub bo’lgan natural sonlar soni quyidagicha topiladi.

Agar n! = ko’rinishda yoyilgan bo’lsa, (bunda p₁, p₂ …….p_k – tub sonlardir)
aniqlanadi. ( [x] – x sonining butun qismi)
Fermning kichik teoremasi
Ixtiyoriy p tub soni va ixtiyoriy a natural soni uchun a^p – a soni p soniga qoldiqsiz bo’linadi.
Yoki yuqoridagi teoremaning boshqacha ko’rinishi quyidagicha;
a^p-1-1 soni p soniga qoldiqsiz bo’linadi. Bunda p tub son va a soni p soniga bo’linmaydi.
Misol: 5¹⁰² sonini 103 ga bo’lgandagi qoldiqni toping.
Yechimi: Fermning kichik teoremasiga asosan 5¹⁰²-1 soni 103 soniga qoldiqsiz bo’linadi. Demak 5¹⁰²-1+1 o’zgartirish kiritib qoldiq 1 bo’lishini ko’rish qiyin emas.
Siz sonlarning eng katta umumiy bo’luvchisini topishda odatda sonlarning kanonik yoyilmasidan foydalanasiz. Ya’ni n sonining kanonik yoyilmasi
n = (bunda p₁, p₂ …….p_k – tub sonlardir).
Lekin sonlarning eng katta bo’luvchisini topish masalasi bevosita Evklid algoritmi tushunchasi bilan bog’liqdir. Ya’ni bu algoritm quyidagicha.
Berilgan a va b (a>b) natural sonlarning eng katta umumiy bo’luvchsi EKUB(a,b) uchun Evklid algoritmidan foydalanamiz, ya’ni:
a = bq₁ + r₁ (0 r₁b = r₁ q₂ + r₂ (0 r₂< r₁)
r₁ = r₂ q₃ + r₃ (0 r₃< r₂)
……………………………..
r_n-2 = r_n-1 q_n + r_n (0 r_n< r_n-1)
r_n-1 = r_n q_n+1 r_n+1=0
Hosil qilingan noldan farqli a va b sonlarning EKUBi r_n = EKUB(a,b) dan iborat bo’ladi.
Misol: Evklid algoritmidan foydalanib EKUB (3n+1;10n+3) ni hisoblang.
Yechim: 10n+3 = (3n+1)*3+n
3n+1=n*3+1
n = 1*n
Demak EKUB (3n+1;10n+3)=1

x haqiqiy sonning butun qismi deb, x dan oshmaydigan eng katta butun songa aytiladi.

X sonining butun qismi [x] ko’rinishida yoziladi.
Misol uchun [3,8] = 4, [-3,8] = -4
Har qanday x haqiqiy son uchun quyidagi tenglik o’rinlidir.
[x] x <[x]+1
X haqiqiy sonining kasr qismi deb, x va uning butun qismi ayirmasiga aytiladi.
X sonining kasr qismi {x} ko’rinishida yoziladi.
Har qanday x haqiqiy son uchun quyidagi tengliklar o’rinlidir.
x = [x] + {x}, {x} = x - [x]
Misol uchun {3,8} = 3,8-3 = 0,8 , {-3,8} = (-3,8) – (-4) =0,2
X haqiqiy sonning butun qismi doimo butun son bo’ladi: Ya’ni [x] Z
X haqiqiy sonning kasr qismi doimo quyidagi shartni qanoatlantiradi.
0 {x}<1
X haqiqiy son va n butun sonlar uchun quyidagi tenglik doimo qanoatlantiradi.
[x+n] = [x] + n
Misol uchun [3,8 + 4] = [3,8]+4