Tub modul bo’yicha sonlar va indekslar jadvali.”

2-misol. 11^x=17 (mod 31) taqqoslamani eching.
Buning uchun berilgan taqqoslamaning ikkala qismini indekslab xind 11≡ ind 17 (mod 30) taqqoslamaga ega bo’lamiz. ind 11 = 23, ind 17=7 ekanidan 23x ≡ 7 (mod 30) yoki x = 29 (mod 30) taqqoslamani hosil qilamiz. Bundan x=29 (mod 30) echim berilgan taqqoslamaning yechimi ekani kelib chiqadi
2.2-§. Tub modul bo’yicha sonlar va indekslar jadvali
Logarifmik jadvallar mavjud bo’lganidek, ixtiyoriy r tub modul bo’yicha indekslar jadvalini tuzish mumkin. Indekslarning asosi qilib r sonning birorta boshlang’ich ildizi olinadi. Dastlabki indekslar jadvalini rus matematigi M. V. Ostrogradskiy tuzgan. U 1837-yilda 200 gacha bo’lgan tub modullar uchun indekslar jadvalini tuzdi. Hozirgi kunda bunday jadvallar 10000 gacha tub modullar uchun tuzilgan.
Har bir jadval quyidagi 2 ta qismdan iboratbo’ladi:

1. 
   berilgan p son bo’yicha I indeksni topish;
   
2. 
   berilgan Iindeks bo’yicha p sonni topish.
   

Biror r modul bo’yicha indekslar jadvalini tuzish uchun avvalo r modul bo’yicha g boshlang’ich ildizni topish lozim. So’ngra
g⁰, g¹, g², … ,g^p–2
darajalar r modul bo’yicha eng kichik musbat chegirmalarga almashtiriladi. Masalan, r=11modul bo’yicha indekslar va ularga mos sonlar jadvalini tuzaylik. Bevosita hisoblash usuli bilan 2, 6, 7, 8lar 11 modul bo’yicha boshlang’ich ildiz ekaniga ishonch hosil qilamiz.
Haqiqatan, φ( 11) = 10 bo’lgani uchun
22(mod11), 2³8(mod11),
2⁴5(mod11), 2²4(mod11),
2⁵l0(modl1), 2¹⁰1( mod 11),
2⁹6 (mod11), 2⁶ 9 (mod11),
2⁷ 7 (mod 11), 2⁸ 3 (mod11)
larga asosan 2 boshlang’ich ildizdir.
66 (mod11), 6³  7 (mod11), 6¹⁰ 1 (mod 11),
6²  3 (mod 11), 6⁵  10 (mod 11).
Demak, 1l modul bo’yicha 6 ham boshlang’ich ildiz ekan.
Endi asos 2 bo’lganida quyidagi jadvallarni tuzamiz:

п	1	2	3	4	5	6	7	8	9	10
1	10	1	8	2	4	9	7	3	6	5

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

Birinchi jadvalga asosan, son berilsa, indeks topiladi, ikkinchi jadvalga asosan esa indeksga qarab son topiladi.
p= 43 modul bo’yicha 3, 5, 12, 18, 19, 20, 26, 28, 30, 33, 34 sonlar boshlang’ich ildizdir. g= 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	37	9	1	25
3	19	32	27	23	13	12	28	35	26	5
4	38	18	21

L	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	36	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) ning o’nlik va birlik xonasini 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, ind₂₈37=35. Endi aksincha 43 modul bo’yicha indeksi 18 ga teng sonmi toping.
Ikkinchi jadvalga asosan birinchi satr va 8- ustunningkesishgan joyiga 41 soni mos keladi. Demak, n=41.
Agarizlanayotgan son (yoki indeks) jadvaldagi eng katta sondan ham katta bo’lsa, bu son qaralayotgan r yoki r–1modul bo’yicha eng kichik musbat chegirma bilan almashtirib olinadi.
Boshlang’ich ildizi mavjud bo’lgan har qanday modul bo’yicha indekslar jadvalini tuzish mumkin. Chunki bunday holda ham boshlang’ich ildizning darajalari m modul bo’yicha chegirmalarning keltirilgan sistemasini tashkil qiladi.
I. Bo’linish alomatlari. Butun sonlar to’plamiga tegishli ixtiyoriy a va m>0sonlari berilgan bo’lsin. Ko’p hollarda a sonni m songa bo’lishdan hosil bo’lgan eng kichik qoldiqni topish talab etiladi. Bu masalani hal etishning umumlashgan usulini dastlab fransuz matematigi B. Paskal ko’rsatgan edi.
Biz hozir shu usulni o’nlik, yuzlik va minglik sanoq sistemalari uchun bayon etamiz.
Faraz qilaylik, a natural son o’nlik sanoq sistemada berilgan bo’lsin. Unda bu asonini o’nning darajalari bo’yicha quyilagicha yozish mumkin:
a= a₀ + a₁10 + a₂10² + ... + a_p10ⁿ.
m modul bo’yicha 10^kson tegishli bo’lgai chegirmalar sinfining eng kichik absolyut chegirmasi r_k, ya’ni
10^k≡ r_k(modm) ( ; r₀=l) bo’lsin.
Unda a sonini quyidagicha yozish mumkin:
a=a₀r₀ + a_lr₁ + . . . + a_nr_n (modm). (1)
Agar R_m = a₀r₀+ a₁r₁+ . . . + a_nr_n.desak, (1) ushbu
a=R_m(modm)
ko’rinishda bo’ladi. Shunday qilib, a soni undan kichik bo’lgan R_m soni bilan almashtiriladi. Boshqacha qilib aytganda, (1) taqqoslama o’nlik sistemada Paskalning bo’linish (yoki teng qoldiqlilik) alomatini bildiradi. Agar R_m=0 bo’lsa, a son m ga qoldiqsiz bo’linadi, agar R_m≠0 bo’lsa, u holda r = R_m bo’ladi.
Bo’linish alomatining quyidagi ba’zi xususiy hollarini ko’rib o’tamiz:

1. 
   m=9 bo’lsin. Biz ixtiyoriy natural sonning 9 ga bo’linish alomatini keltirib chiqaramiz.
   

Ushbu 10≡ l (mod9) taqqoslamaning ikkala qismini k darajaga ko’tarsak,
10^k=1 (mod9)
taqqoslama hosil bo’ladi. Bundan ko’rinadiki, barcha r_k lar 1ga teng ekan. Unda R_mquyidagi ko’rinishni oladi:
R₉= a₀+ a₁ + a₂ + ... + a_n
Bu esa o’rta maktabda bizga ma’lum bo’lgan alomatning o’zidir, ya’ni berilgan sonning raqamlari yig’indisi 9 ga bo’linsa, u holda bu natural son 9 gabo’linadi.

2. 
   m=11bo’lsin. U holda 10 ≡ –l (mod 11)  10^k≡ (–l)^k(mod 11) ga asosan
   

R₁₁ = (a₀+ a₂ + a₄ + …) –(a₁ + a₃ + a₅ + … )
tenglik o’rinli bo’ladi, ya’ni R₁₁son 11 ga bo’linsa, u holda berilgan son 11 ga bo’linadi.
1-misol.a = 3568921 sonni 11 ga bo’lganda hosil bo’ladigan qoldiqni toping.
Demak, 3568921 sonni 11 ga bo’lganda qoladigan qoldiq 4 ga teng.

3. 
   m = 7 bo’lsin. U holda
   

10⁰ ≡ l (mod 7), 10 ≡ 3(mod 7), 10² ≡ 2(mod7),
10³ ≡ -1 (mod 7), 10⁴ ≡ –3 (mod 7), 10⁵ ≡ –2(mod 7),
10⁶ ≡ 1 (mod 7)
bo’lgani uchun R₁ = a₀+ 3a₁+ 2a₂ – a₃ – 3a₄ – 2a₅+ a₆ bo’ladi. Faraz qilaylik, 10 soni m modul bo’yicha δ ko’rsatkichga tegishli bo’lsin. Unda ko’rsatkichning ta’rifiga asosan, 10⁰ ≡ l(mod m) bo’lgani uchun r_δ= 1 bo’lib, r_δ+1 = r₁, r_δ+2= r₂, . . , , r_2δ = r_δ= 1 bo’ladi, ya’ni qoldiqlar δ ta qadamdan so’ng takrorlanadi. U holda R_m quyidagi ko’rinishni oladi:
R_m=a₀ + a₁r₁+ a₂r₂ + … + a_δ-1r_δ-1+ a_δ +a_δ+1r₁+…
Ma’lumki, ixtiyoriy sonni ixtiyoriy sanoq sistemasida yozish mumkin. Faraz qilaylik, sanoq sistemasining asosi 10^δ bo’lib, bu asosga ko’ra a sonining yoyilmasi a=d₀ + d₁10^δ + d₂10^2δ + . . . + d_n10^nδ
bo’lsin. (10)ⁿ=l(modm) bo’lgani uchun (1) taqqoslama a= d₀+ d₁+ d₂+ . . . + d_nko’rinishni oladi.
Demak, 10 asosli sistemada berilgan sonning mga bo’linish alomati o’nlik sistemada berilgan sonning 9 ga bo’linish alomati kabi bo’lar ekan. Shuni alohida ta’kidlash kerakki, berilgan a sonining 10^δ asos bo’yicha mga bo’linish alomatini keltirib chiqarish uchun uni o’ngdan chapga qarab δ xonalarga ajratib chiqish lozim.
Endi darajani bo’lishdan chiqqan qoldiqni hisoblaylik.
a ≡ r (modm) a^k ≡ r^k (modm)
bo’lgani uchun a^k daraja r^k daraja bilan almashtiriladi
(r;m)=1 bo’lganda Eyler teoremasidan foydalanish maqsadga muvofiqdir. Haqiqatan, (r; m)=1 bulganda r^φ(m)=1(mod m) edi. k= φ(m)q+ l (0 ≤ l <φ(m)) tenglikka asosan r^k ≡ (r ^φ(m))^q r^l ≡ r^l (mod m) ni yoza olamiz.