Mavzu: Tub modul bo’yicha indekslar, ularning tadqiqlari

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 <sup>(</sup>𝑝 − 1<sup>)</sup>! + 1 ham 𝑝 ga bo`linadi, ya`ni <sup>(</sup>𝑝 − 1<sup>)</sup> + 1 ≡ 0(𝑚𝑜𝑑𝑝)
MISOL. 1) 1 ∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 + 1 ≡ 0<sup>(</sup>𝑚𝑜𝑑7<sup>)</sup>
2) 4! + 1 = 24 + 1 ≡ 0<sup>(</sup>𝑚𝑜𝑑5<sup>)</sup>
MISOL. 251𝑥<sup>54</sup> + 63𝑥<sup>25</sup> − 7𝑥<sup>11</sup> + 4𝑥<sup>3</sup> + 2 ≡ 0<sup>(</sup>𝑚𝑜𝑑 5<sup>)</sup> taqqoslamani soddalashtiring.
Yechish: berigan taqqoslamani soddalashtirish uchun taqqoslamalar xossalaridan va Eyler teoremasidan foyalanamiz:
251 ≡ 1<sup>(</sup>𝑚𝑜𝑑 5<sup>)</sup>;
63 ≡ 3<sup>(</sup>𝑚𝑜𝑑 5<sup>)</sup>;
7 ≡ 2<sup>(</sup>𝑚𝑜𝑑 5<sup>)</sup>;
4 ≡ 4<sup>(</sup>𝑚𝑜𝑑 5<sup>)</sup>;
2 ≡ 2<sup>(</sup>𝑚𝑜𝑑 5<sup>)</sup>.
𝜑<sup>(</sup>5<sup>)</sup> = 4 dan: 𝑥<sup>54</sup> ≡ (𝑥<sup>4</sup>)<sup>13</sup> ∙ 𝑥<sup>2</sup> ≡ 𝑥<sup>2(</sup>𝑚𝑜𝑑 5<sup>)</sup>; 𝑥<sup>25</sup> ≡ (𝑥<sup>4</sup>)<sup>6</sup> ∙ 𝑥 ≡ 𝑥<sup>(</sup>𝑚𝑜𝑑 5<sup>)</sup>;
𝑥<sup>11</sup> ≡ (𝑥<sup>4</sup>)<sup>2</sup> ∙ 𝑥<sup>3</sup> ≡ 𝑥<sup>3(</sup>𝑚𝑜𝑑 5<sup>)</sup>.
Keltirilgan taqqoslamalar yordamida berilgan taqqoslamani soddalashtiramiz:
251𝑥<sup>54</sup> + 63𝑥<sup>25</sup> − 7𝑥<sup>11</sup> + 4𝑥<sup>3</sup> + 2 ≡ 𝑥<sup>2</sup> + 3𝑥 − 2𝑥<sup>3</sup> + 4𝑥<sup>3</sup> + 2 ≡ 2𝑥<sup>3</sup> + 𝑥<sup>2</sup> +
3𝑥 + 2 ≡ 0 (𝑚𝑜𝑑 5).
Sonning ko’rsatkichi. Tub modul bo’yicha indekslar. Ikki hadli taqoslamalar.
<sup>(</sup>𝑎, 𝑚<sup>)</sup> = 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. 𝑎<sup>𝛾</sup> ≡ 1(𝑚𝑜𝑑𝑚) bo`lishi uchun 𝛾 sonning 𝛿 ga bo`linishi zarur va etarli. (𝛿 son − 𝑎 sonning m modul` bo`yicha ko`rsatkichi).
Haqiqatan, 𝑟 𝑣𝑎 𝑟₁ sonlar 𝛾 va 𝛾^′ sonlarning 𝛿 ga bo`lgandagi qoldiqlari bo`lsin, u holda qandaydir 𝑞 va 𝑞₁ sonlar uchun
𝛾 = 𝛿𝑞 + 𝑟 𝖠 𝛾^′ = 𝛿𝑞₁ + 𝑟₁

o`rinli bo`lib,

𝑎^𝛾 = (𝑎^𝛿)^𝑞 ∙ 𝑎^𝑟 ≡ 𝑎^𝑟(𝑚𝑜𝑑𝑚⁾

𝑎^𝛾𝘍 = (𝑎^𝛿)^𝑞1 ⋅ 𝑎^𝑟1 ≡ 𝑎^𝑟1 (𝑚𝑜𝑑𝑚)

Demak, 𝑎^𝛾 ≡ 𝑎^𝛾𝘍(𝑚𝑜𝑑𝑚) bo`lishi uchun

𝑎^𝑟 ≡ 𝑎^{𝑟1 (}𝑚𝑜𝑑𝑚⁾ ya`ni
𝑟 = 𝑟₁

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. 1, 𝑎, 𝑎², … , 𝑎^𝛿−1 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
2<sup>3</sup> ≡ 1(𝑚𝑜𝑑7) demak, 2<sup>2</sup> = 4 ham 7 modul` bo`yicha 3 ko`rsatkichga tegishli,

ya`ni 4³ ≡ (2³)² ≡ 1(𝑚𝑜𝑑7) chunki, ⁽2,3⁾ = 1 𝖠 ^𝛿
(𝑘,𝛿)
= 𝛿

2) 3 soni 7 modul bo`yicha 6 ko`rstgichga tegishli, ya`ni

3⁶ ≡ ⁽3²⁾³ ≡ 2³ ≡ 1⁽𝑚𝑜𝑑7⁾

3⁴ = 81 esa ^𝛿
(𝑘,𝛿)
⁽−1⁾⁴ ≡ 1(𝑚𝑜𝑑7)
₌ 6
(4,6)
= ⁶ = 3 ko`rsatgichga tegishli, ya`ni 81³ = (3⁴)³ ≡
2

NATIJA. Agar (𝑘, 𝛿) = 1 bo`lsa, 𝑎<sup>𝑘</sup> 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 𝜑<sup>(</sup>𝑚<sup>)</sup> = 𝜑<sup>(</sup>43<sup>)</sup> = 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¹ ≡ 7⁽𝑚𝑜𝑑43⁾

7² ≡ 6⁽𝑚𝑜𝑑43⁾
7³ ≡ ⁽−1⁾⁽𝑚𝑜𝑑43⁾
7⁶ ≡ 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)
𝑥⁶ ≡ 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
7⁰, 7¹, 7², 7³, 7⁴, 7⁵

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

nitekshiramiz.
7¹, 7⁵
7¹ ≡ 7(𝑚𝑜𝑑43)
7⁵ ≡ 7² ⋅ 7² ⋅ 7 ≡ 6 ⋅ 6 ⋅ 7 ≡ 252 ≡ 37(𝑚𝑜𝑑43)

Demak, 7^̅ 𝖠 3^̅̅̅7^̅ sinflar 43 modul` bo`yicha 6 ko`rsatgichga tegishli.
TA`RIF. Agar a sonning m modul` bo`yicha ko`rsatkichi <sup>(</sup>𝑚<sup>)</sup> 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 𝑔⁰, 𝑔¹, … , 𝑔^𝑝−2 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⁾, 2³ ≡ 8⁽𝑚𝑜𝑑 11⁾, 2⁴ ≡ 5⁽𝑚𝑜𝑑 11⁾,
2² ≡ 4 ⁽𝑚𝑜𝑑 11⁾, 2⁵ ≡ 10 ⁽𝑚𝑜𝑑 11⁾,
2¹⁰ ≡ 1 ⁽𝑚𝑜𝑑 11⁾, 2⁹ ≡ 6⁽𝑚𝑜𝑑 11⁾, 2⁶ ≡ 9 ⁽𝑚𝑜𝑑 11⁾,
2⁷ ≡ 7 ⁽𝑚𝑜𝑑 11⁾, 2⁸ ≡ 3 ⁽𝑚𝑜𝑑 11⁾
larga asosan 2 boshlang’ich ildizir.
6 ≡ 6 ⁽𝑚𝑜𝑑 11⁾, 6² ≡ 3 ⁽𝑚𝑜𝑑 11⁾, 6³ ≡ 7⁽𝑚𝑜𝑑 11⁾, 6⁴ ≡ 9 ⁽𝑚𝑜𝑑 11⁾,
6⁵ ≡ 10 ⁽𝑚𝑜𝑑 11⁾, 6¹⁰ ≡ 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, 𝑖𝑛𝑑₄₃37 = 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.