Taqqoslamalar va ularning tadbiqlari

Tub modul bo’yicha yuqori darajali taqqoslamalar.
TA`RIF. Agar , 𝑎𝑛−1, … 𝑎1, 𝑎0 sonlar butun sonlar, p-tub son, 𝑎𝑛 son 𝑝 ga bo`linmasa
𝑎𝑛𝑥𝑛 + 𝑎𝑛−1𝑥𝑛−1 + ⋯ + 𝑎1𝑥 + 𝑎0 ≡ 0(𝑚𝑜𝑑𝑝) (1)
taqqoslama 𝑝 −tub modulli 𝑛 −darajali taqqoslama deyiladi.
1-TEOREMA. (1) taqqoslama, ya`ni tub modulli 𝑛 −darajali taqqoslama yechimlari soni 𝑛 tadan ortiq emas.
ISBOTI. 𝑛 ga nisbatan induksiya metodidan foydalanamiz. Agar 𝑛 = 0 bo`lsa, u holda 𝑎0 ≡ 0(𝑚𝑜𝑑𝑝) ∧ 𝑎0 ∤ 𝑝 bo`lib, berilgan taqqoslama 0 ta yechimga ega. Faraz qilaylik (1) taqqoslamaning darajasi 𝑛 > 0 bo`lsin. Agar bu taqqoslama yechimga ega bo`lsa, u holda ∃𝑥1 son uchun
𝑎𝑛𝑥1𝑛 + 𝑎𝑛−1𝑥1𝑛−1 + ⋯ + 𝑎1𝑥1 + 𝑎0 ≡ 0(𝑚𝑜𝑑𝑝) (2)
o`rinli bo`ladi. (1) dan (2) ni ayiramiz, u holda 𝑘-darajali hadlar ayirmasi
𝑎𝑘(𝑥𝑘 − 𝑥1𝑘) = 𝑎𝑘(𝑥 − 𝑥1)(𝑥𝑘−1 + 𝑥𝑘−2𝑥1 + 𝑥𝑘−3𝑥12 + ⋯ + 𝑥𝑥1𝑘−2 + 𝑥1𝑘−2)
𝑘 = 1,2,… , 𝑛 da har bir ayirma (𝑥 − 𝑥1) ko`paytuvchiga ega bo`ladi. Shuning uchun natijani
(𝑥 − 𝑥1) ∙ (𝑏𝑛−1𝑥𝑛−1 + ⋯ + 𝑏2) ≡ 0(𝑚𝑜𝑑𝑝) (3)
ning ∀ boshqa 𝑥2 yechimi
𝑏𝑛𝑥𝑛−1 + ⋯ + 𝑏1𝑥 + 𝑏0 ≡ 0(𝑚𝑜𝑑𝑝) (4)
taqqoslamaning yechimi bo`ladi.
(4) ning darajasi 𝑛 −dan kichik bo`lgani uchun uning yechimlari soni 𝑛 − 1 dan katta emas, demak (1) ning yechimalri soni 𝑛 tadan ko`p emas. ⁵
1-NATIJA. Agar 𝑎𝑛𝑥𝑛 + ⋯ + 𝑎1𝑥 + 𝑎0 ≡ 0(𝑚𝑜𝑑𝑝) taqqoslama 𝑛 tadan ortiq yechimga ega bo`lsa, u holda uning barcha koeffitsientlai 𝑝 ga bo`linadi.
Haqiqatan, (1) taqqoslama kamida 𝑛 + 1 ta yechimga bo`lsin va
𝑥1, 𝑥2, … , 𝑥𝑛, 𝑥𝑛+1 lar bu yechimlarning bittadan chegirmalari bo`lsin, u holda 𝑓(𝑥) ni quyidagi ko`rinishda yoza olamiz.
𝑓(𝑥) = 𝑎(𝑥 − 𝑥1)(𝑥 − 𝑥2) … (𝑥 − 𝑥𝑛−1)(𝑥 − 𝑥𝑛) + 𝑏(𝑥 − 𝑥1)(𝑥 − 𝑥2) … (𝑥 −
𝑥𝑛−1) + 𝑐(𝑥 − 𝑥1)(𝑥 − 𝑥2) … (𝑥 − 𝑥𝑛−2) + ⋯ + 𝑘(𝑥 − 𝑥1)(𝑥 − 𝑥2) +
𝑙(𝑥 − 𝑥1) + 𝑚 (2)
ga ketma-ket 𝑥 = 𝑥1, 𝑥2, … , 𝑥𝑛, 𝑥𝑛+1 larni qo`yib, barcha
𝑚, 𝑙, 𝑘, … , 𝑐, 𝑏, 𝑎 larning 𝑝 ga karrali ekanini ko`ramiz. Demak, barcha 𝑎0, 𝑎1, … , 𝑎𝑛 lar ham 𝑝 ga karrali.
2-TEOREMA. Agar 𝑝 −tub son bo`lsa, u holda 𝑥𝑝−1 − 1 ≡ 0(𝑚𝑜𝑑𝑝) taqqoslama 𝑝 − 1 ta yechimga ega bo`ladi.
ISBOTI. Ferma teoremasiga ko`ra, 𝑥𝑝 = 𝑥(𝑚𝑜𝑑𝑝) yoki 𝑥𝑝−1 ≡ 1(𝑚𝑜𝑑𝑝) bo`lib, uning yechimlari esa, 𝑝 ga bo`linmaydigan 1,2,… , 𝑝 − 1 lardan iborat bo`ladi.
Masalan, 𝑥7−1 ≡ 1(𝑚𝑜𝑑7)
𝑥6 ≡ 1(𝑚𝑜𝑑7) taqqoslamaning yechimlari, 1,2,3,4,5,6 bo`ladi.
3-TEOREMA. (1) taqqoslama darajasi 𝑝 − 1 dan katta bo`lmagan taqqoslamaga teng kuchli.
ISBOTI. 𝑓(𝑥) ni 𝑥𝑝 − 𝑥 ga bo`lib,
𝑓(𝑥) = (𝑥𝑝 − 𝑥)𝑎(𝑥) + 𝑅(𝑥)
ga ega bo`lamiz. 𝑅(𝑥) ning darajasi 𝑝 − 1 dan katta emas. Ferma teoremasiga ko`ra,
𝑥𝑝 − 𝑥 ≡ 0(𝑚𝑜𝑑𝑝)
taqqoslama o`rinli bo`lgani uchun 𝑓(𝑥) ≡ 𝑅(𝑥)(𝑚𝑜𝑑𝑝) taqqoslama o`rinli.
4-TEOREMA. (Vil`son teoremasi). 𝑝 tub son uchun
(𝑝 − 1)! + 1 ≡ 0(𝑚𝑜𝑑𝑝)
taqqoslama o`rinli.
ISBOTI. 𝑝 = 2 uchun teorema o`rinli. Agar > 2 bo`lsa,
(𝑥 − 1)(𝑥 − 2) … (𝑥 − (𝑝 − 1)) − (𝑥𝑝−1 − 1) ≡ 0(𝑚𝑜𝑑𝑝)
taqqoslamani qarasak, uning darajasi 𝑝 − 2 dan katta emas va u 𝑝 − 1 ta yechimga ega. (yechim 1,2,…,p-1 lardan iborat). Demak, 1-natijaga ko`ra, uning barcha koeffitsientlari, jumladan uning ozod hadi (𝑝 − 1)! + 1 ham 𝑝 ga bo`linadi, ya`ni (𝑝 − 1) + 1 ≡ 0(𝑚𝑜𝑑𝑝)
MISOL. 1) 1 ∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 + 1 ≡ 0(𝑚𝑜𝑑7)
2) 4! + 1 = 24 + 1 ≡ 0(𝑚𝑜𝑑5)
MISOL. 251𝑥54 + 63𝑥25 − 7𝑥11 + 4𝑥3 + 2 ≡ 0(𝑚𝑜𝑑 5) taqqoslamani soddalashtiring.
Yechish: berigan taqqoslamani soddalashtirish uchun taqqoslamalar xossalaridan va Eyler teoremasidan foyalanamiz:
251 ≡ 1(𝑚𝑜𝑑 5);
63 ≡ 3(𝑚𝑜𝑑 5);
7 ≡ 2(𝑚𝑜𝑑 5);
4 ≡ 4(𝑚𝑜𝑑 5);
2 ≡ 2(𝑚𝑜𝑑 5).
𝜑(5) = 4 dan: 𝑥54 ≡ (𝑥4)13 ∙ 𝑥2 ≡ 𝑥2(𝑚𝑜𝑑 5); 𝑥25 ≡ (𝑥4)6 ∙ 𝑥 ≡ 𝑥(𝑚𝑜𝑑 5); 𝑥11 ≡ (𝑥4)2 ∙ 𝑥3 ≡ 𝑥3(𝑚𝑜𝑑 5).
Keltirilgan taqqoslamalar yordamida berilgan taqqoslamani soddalashtiramiz:
251𝑥54 + 63𝑥25 − 7𝑥11 + 4𝑥3 + 2 ≡ 𝑥2 + 3𝑥 − 2𝑥3 + 4𝑥3 + 2 ≡ 2𝑥3 + 𝑥2 +
3𝑥 + 2 ≡ 0 (𝑚𝑜𝑑 5).
Sonning ko’rsatkichi. Tub modul bo’yicha indekslar. Ikki hadli taqoslamalar.
(𝑎, 𝑚) = 1 bo’lganda, Eyler teoremasiga ko`ra,
𝑎𝜑(𝑚) ≡ 1(𝑚𝑜𝑑𝑚)
o`rinli.
TA`RIF. (𝑎, 𝑚) = 1 bo`lib
𝑎𝛿 ≡ 1(𝑚𝑜𝑑𝑚)
taqqoslamani qanoatlantiruvchi eng kichik 𝛿 son a sonning 𝑚 modul` bo`yicha ko`rsatkichi deyiladi.
TEOREMA. 𝑎𝛾 ≡ 1(𝑚𝑜𝑑𝑚) bo`lishi uchun 𝛾 sonning 𝛿 ga bo`linishi zarur va etarli. ( son − 𝑎 sonning m modul` bo`yicha ko`rsatkichi).
Haqiqatan, 𝑟 𝑣𝑎 𝑟1 sonlar 𝛾 va 𝛾′ sonlarning 𝛿 ga bo`lgandagi qoldiqlari bo`lsin, u holda qandaydir 𝑞 va 𝑞1 sonlar uchun
𝛾 = 𝛿𝑞 + 𝑟 ∧ 𝛾′ = 𝛿𝑞1 + 𝑟1
o`rinli bo`lib,
𝑎𝛾 = (𝑎𝛿)𝑞 ∙ 𝑎𝑟 ≡ 𝑎𝑟(𝑚𝑜𝑑𝑚)
𝑎𝛾′ = (𝑎𝛿)𝑞1 ⋅ 𝑎𝑟1 ≡ 𝑎𝑟1(𝑚𝑜𝑑𝑚)
Demak, ≡ 𝑎𝛾′(𝑚𝑜𝑑𝑚) bo`lishi uchun
𝑎𝑟 ≡ 𝑎𝑟1(𝑚𝑜𝑑𝑚) ya`ni
𝑟 = 𝑟1
bo`lishi zarur va etarli.
Agar 𝛾′ = 0 desak,
𝛾 ≡ 𝛾′(𝑚𝑜𝑑𝛿)
dan 𝛾 ning 𝛿 ga bo`linishi kelib chiqadi.
1-NATIJA. 𝑎𝑠 ≡ 𝑎𝑡(𝑚𝑜𝑑𝑚) taqqoslamaning o`rinli bo`lishi uchun 𝑠 − 𝑡 ning 𝛿 ga bo’linishi zarur va etarli.
2-NATIJA. sonlar m modul` bo`yicha o`zaro taqqoslanmaydi.
TEOREMA. 𝑎𝑘 sonning 𝑚 modul` bo`yicha ko`rsatkichi 𝛿/(𝑘, 𝛿) ga teng.
MISOL. 1) 2 son 7 modul` bo`yicha, 3 ko`rsatkichga tegishli, ya`ni
23 ≡ 1(𝑚𝑜𝑑7) demak, 22 = 4 ham 7 modul` bo`yicha 3 ko`rsatkichga tegishli, ya`ni 43 ≡ (23)2 ≡ 1(𝑚𝑜𝑑7) chunki,
2) 3 soni 7 modul bo`yicha 6 ko`rstgichga tegishli, ya`ni
36 ≡ (32)3 ≡ 23 ≡ 1(𝑚𝑜𝑑7)
34 = 81 esa ko`rsatgichga tegishli, ya`ni 813 = (34)3 ≡
(−1)4 ≡ 1(𝑚𝑜𝑑7)
NATIJA. Agar (𝑘, 𝛿) = 1 bo`lsa, 𝑎𝑘 sonning modul` bo`yicha ko`rsatkichi 𝛿 ga teng.
NATIJA. 1, 𝑎, … , 𝑎𝛿−1 sonlar orasida 𝜑(𝛿) ta m modul` bilan o`zaro taqqoslanmaydigan ko`rsatkichi 𝛿 ga teng bo`lgan sonlar mavjud.
MISOL. 7 chegirmalar sinfining 43 modul` bo`yicha ko`rsatkichini va shu modul` bo`yicha 7 sinfning ko`rsatkichiga teng bo`lgan barcha chegirmalar sinfini topamiz.
Ma`lumki, ixtiyoriy sinfning ko`rsatkichi 𝜑(𝑚) = 𝜑(43) = 42 ning bo`luvchisi bo`ladi. 42 ning natural bo`luvchilari 1,2,3,6,7,14,21,42 bo`ladi. 7 ni ketma ket shu darajalarga ko`tarib, 1 bilan taqqoslanuvchi sonni topamiz.
≡ 7(𝑚𝑜𝑑43)
≡ 6(𝑚𝑜𝑑43)
≡ (−1)(𝑚𝑜𝑑43)
76 ≡ 1(𝑚𝑜𝑑43)
Demak, 7 ning 43 modul` bo`yicha ko`rsatkichi 6 ga teng: 𝛿 = 6
Endi 43 modul` bo`yicha chegirmalarning to`la sistemasidagi sinflarning qaysilari 6 ko`rsatgichga tegishli ekanini topamiz.
Buning uchun 0,1,2,3,4,5 (1) sonlarni tanlab olamiz va ular orasidan
6 bilan o’zaro tub bo’lgan sonlarni ajratib olamiz. 6 ko`rsatkichga 43 modul` bo`yicha tegishli sonlar (sinflar)
𝑥6 ≡ 1(𝑚𝑜𝑑43)
taqqoslamani qanoatlantirishi kerak, ya`ni shu taqqoslamaning yechimlarigina 43 modul` bo`yicha 6 ko`rsatkichiga tegishli bo`lishi mumkin. Uning yechimlari esa 43 modul` bo`yicha

sonlari orasida bo`ladi. (1) ketma ketlikda 6 bilan o`zaro tub sonlar 1,5 bo`lgani uchun

nitekshiramiz.
71 ≡ 7(𝑚𝑜𝑑43)
75 ≡ 72 ⋅ 72 ⋅ 7 ≡ 6 ⋅ 6 ⋅ 7 ≡ 252 ≡ 37(𝑚𝑜𝑑43)
Demak, 7̅ ∧ 37̅̅̅̅ sinflar 43 modul` bo`yicha 6 ko`rsatgichga tegishli.
TA`RIF. Agar a sonning m modul` bo`yicha ko`rsatkichi 𝜑(𝑚) ga teng bo`lsa a ga m modul` bo`yicha boshlang`ich ildiz deyiladi.
TA`RIF. Agar g son p tub modul` bo`yicha boshlang`ich ildiz bo`lib,
(𝑎, 𝑝) = 1 bo`lganda
𝑎 ≡ 𝑔𝛾(𝑚𝑜𝑑𝑝) (2)
taqqoslama o`rinli bo`lsa, 𝛾 ≥ 0 son a sonning p modul` bo`yicha g asosga nisbatan indeksi deyiladi va uni
𝛾 = 𝑖𝑛𝑑𝑔𝑎
kabi belgilanadi.
Bu ta`rifdan foydalanib, (2) ni
𝑎 ≡ 𝑔𝑖𝑛𝑔𝑎(𝑚𝑜𝑑𝑝)
kabi yozish mumkin.
Logarifmik ladvallar mavjud bo’lganidek, ixtiyoriy p tub modul bo’yicha indekslar jadvalini tuzish mukin. Indekslarning asosi qilib p sonning birorta bshlang’ich ildizi olinadi. Har bir jadval quyidagi 2 ta qimdan iborat bo’ladi:
1) Berilgan n son bo’yicha I indeksni topish 2) Berilgan I indeks bo’yicha n sonni topish.
Biror p modul bo’yicha indekslar jadvalini tuzish uchun avvalo p modul bo’yicha g boshlang’ich ildizlarni topish lozim. Songra darajalar p modul bo’yicha eng kichik musbat chegirmalarga almashtiriladi. Masalan p=11 modul bo’yicha indekslar va ulara mos sonlar jadvalini tuzaylik. Bevosita hisoblash usuli bilan 2, 6, 7, 8 lar 11 modul bo’yicha boshlang’ich ildiz ekaniga ishonch hosil qilamiz. ⁶
Haqiqatan, (11) = 10 bo’lgni uchun
2 ≡ 2 (𝑚𝑜𝑑 11), 23 ≡ 8(𝑚𝑜𝑑 11), 24 ≡ 5(𝑚𝑜𝑑 11),
22 ≡ 4 (𝑚𝑜𝑑 11), 25 ≡ 10 (𝑚𝑜𝑑 11),
210 ≡ 1 (𝑚𝑜𝑑 11), 29 ≡ 6(𝑚𝑜𝑑 11), 26 ≡ 9 (𝑚𝑜𝑑 11), 27 ≡ 7 (𝑚𝑜𝑑 11), 28 ≡ 3 (𝑚𝑜𝑑 11)
larga asosan 2 boshlang’ich ildizir.
6 ≡ 6 (𝑚𝑜𝑑 11), 62 ≡ 3 (𝑚𝑜𝑑 11), 63 ≡ 7(𝑚𝑜𝑑 11), 64 ≡ 9 (𝑚𝑜𝑑 11),
65 ≡ 10 (𝑚𝑜𝑑 11), 610 ≡ 1 (𝑚𝑜𝑑 11)
Demak, 11 modul bo’yicha 6 ham boshlang’ich ildiz ekan. Endi asos 2 bo’lganda quyidagi jadvallarni tuzamiz:

n	1	2	3	4	5	6	7	8	9	10
I	10	1	8	2	4	9	7	3	6	5
I	1	2	3	4	5	6	7	8	9	10
n	2	4	8	5	10	9	7	3	6	1

Birinchi jadvalga asosan, son berilsa, indeks topiladi, ikkinhi jadvalga asosan esa indeksga qarab son topiladi.
𝑝 = 43 modul bo’yicha 3, 5, 12, 18, 19, 20, 26, 28, 30, 33, 34 sonlar boshlang’ich ildizdir. 𝑔 = 28 bo’lganda quyidagi jadvallarga ega bo’lamiz:

n	0	1	2	3	4	5	6	7	8	9
0		42	39	17	36	5	4	7	33	34
1	2	6	11	40	4	22	30	16	31	29
2	41	24	3	20	8	10	7	9	1	25
3	19	32	27	23	13	12	28	35	26	5
4	38	18	21

I	0	1	2	3	4	5	6	7	8	9
0		28	10	22	14	5	11	7	24	27
1	25	12	35	34	6	39	17	3	41	30
2	23	42	15	33	21	29	38	32	6	14
3	16	18	31	8	9	37	4	26	40	2
4	13	20	1

Bu jadvallardagi satrlar va ustunlar mos ravishda son (indeks) nng o’nlik va birlik xonaini bildirib, ularning kesishgan joyida izlanayotgan indeks (son) turadi.
Misol. 43 modul bo’yicha 37 sonning indeksini toping.
Birinchi jadvaldagi 3-satr va 7-ustunning kesishgan joyida 35 soni joylashgan.
Demak, 𝑖𝑛𝑑4337 = 35. Endi aksincha 43 modul bo’yicha indeksi 18 ga teng sonni toping. 𝑖𝑛𝑑 𝑛 ≡ 18 (𝑚𝑜𝑑 43) . ikkinchi jadvaga asosan birinchi satr va 8-ustunning kesishgan joyida 41 soni mos keladi. Demak, n=41.
Agar izlanayotgan son (yoki indeks) jadvaldagi eng katta sondan ham katta bo’lsa, bu son qaralayotgan p yoki p-1 modul bo’yicha eng kichik musbat chegirma bilan almashtirib olinadi.
Boshlang’ich ildiz mavjud bo’lgan har qanday modul bo’yicha indekslar jadvalini tuzish mumkin. Chuki bunday holda ham boshlang’ich ildizning darajalari m modul bo’yicha chegirmalarning keltirilan sistemasini tashkil qiladi. ⁷