22-мавзу: биринчи даражали бир номаълумли танқосламаларнинг эчимлари сони ҳАҚидаги теорема. 1-таъриф

3-мисол. 17 модуль бўйича 7 сони тегишли бўлган кўрсаткични топинг.
φ(17) = 16 бўлиб, 16 нинг бўлувчилари 1,2,4,8,16 бўлади. Шунинг учун қуйидагиларни ҳисоблаймиз:
7¹ ≡ 7 (mod 17), 7² ≡ - 2 (mod 17),
7⁴ ≡ 4 (mod 17), 7⁸ ≡- 1 (mod 17),
7¹⁶ ≡ 1 (mod 17).
Демак, 7 сони 17 модуль бўйича бошланғич илдиз экан.
5-натижа. Aгap а сон m модуль бўйича δ кўрсаткичга тегишли бўлса, a^k сони шу модуль бўйича кўрсаткичга тегишли бўлади.
Исботи. a^k сон m модуль бўйича γ кўрсаткичга тегишли бўлсин, яъни a^kγ≡l (modт) бажарилсин. 3-натижага асосан, охирги таққослама фақаг kγ≡ 0 (modδ) бўлгандагина ўринли бўлади.
Таққосламаларнинг хоссасига асосан охирги таққосламани қуйидаги кўринишда ёзамиз:
6-натижа. Aгap (δ; k) = 1 бўлса, у ҳолда a^k сон δ кўрсаткичга тегишли бўлади.
4-мисол. 3 сони 7 модуль бўйича 6 кўрсаткичга тегишли, Чунки 3⁴ = 81 сони бўлгани учун 7 модуль бўйича 3 кўрсаткичга тегишли бўлади.
Ҳақиқатан,
81 ≡ –3 (mod7), 81² ≡ 2 (mod7), 81³ ≡ 1 (mod7).
34-§. Кўрсаткичга тегишли синфларнинг мавжудлиги
ва сони. Туб модуль бўйича бошланғич илдизнинг
мавжудлиги
Айтайлик, бирор а сон 8 кўрсаткичга тегишли бўл- син. Чегирмаларнинг келтирилган системасидаги сон- лардан шу 8 кўрсаткичга тегишли бўлганларини топиш бмлан шучндланамиз. Маълумки, р модуль бўйича 8
кўрсаткичга тегишли чегирмалар
.X⁵ = I (modp) П)
таққосламаларнинг ечинлари ичида ётади, (1) таққос- ламанинг ечимлари эса чегирмалари
а°, а¹, а\ .. . , a^k, .... а~¹ (2)
дан ва р модуль бўйича тузилган синфлардан иборат.

Ҳақиқатан, 1) (a^k)° = (a')^k = 1 (mod р) бўлгани учун (2) система (1) ни қаноатлантиради.

(2) қаторнинг ҳар бир элементи 33-§ даги 2-те- оремага асосан, р модуль бўйича турли синфларга те- гишлидир.
(2) да бу чегирмалар сони 8 га тенг,
(1) таққосламада модуль туб бўлгани учун унинг ечимлари сони 8 дан ортиқ эмас. Энди биз топилган ечимлар ичидан кўрсаткичга тегишли бўлганларини излаймиз.
Маълумки, 33-§ даги 1- теоремада бир хил кўрсат- кичга тегишли бўлган чегирмалар синфи' ҳақида гап борган эди, яъни ҳар бир синфнинг барча чегирмалари битта кўрсаткичга тегишли бўлиб, бу кўрсатгич с?|m) нинг бўлувчасидап иборат бўларди. Энди масалани ак- синча қўямиз:


<Р(m) нинг ҳар бир бўлувчиси m модуль бўйича ту- зилган бирор синфнинг кўрсаткичи бўладями? Ҳар қан- дай m модуль бўйича бошланғич илдиз мавжудми? Бу саволларга қуйидаги лемма ёрдамида жавоб бериш мумкин.


Jle м м а. р туб сон ва 8 сон р – 1 соннинг бўлув- шси бўлсин. р модуль бўйиш чегармаларнинг кел- тирилган синфлар системасида 8 кўрсатгичга тегиш- ли. синфлар сони <р(8) та бўлади.
Исботи. Маълумки, р модуль бўйича чегирмалар келгирилган системасининг ҳар бир чегирмаси битта кўрсаткичга тегишли (33-§ га қаранг) ва ҳар бир че- гирмага эса битта скнф мос келади.


р модуль бўйича тузилган чегирмаларнинг келтирил- ган системасидаги чегирмалардан берилган кўрсаткичга тегишли бўлган чегирмалар сонини ф(В) деб бедгилай- лик. Бунда қуйидаги икки ҳол бўлади:


а) 8 кўрсаткичга тегишли бўлган чегирма мавжуд эмас, яъни 8) = 0;
б) келтирилган системанинг камнда битга чегирма- си 3 кўрсаткичга тегишли, яъни ф (S) >0.
Биз б) ҳолни атрофлича қараб чиқайлик. 33-§ даги 6- натижага асосан (3; k) – 1 шартни цаноатлантирувчи барча a^k лар 3 кўрсаткичга тегишли бўлади. (2) цатор- даги (8; k) = 1 шартни қаноатлантирувчи чегирмалар сони tp(8) бўлади. Чунки k ўзгарувчи 0, 1, 2, ,
8 – 1 ларни қабул қилади. Бу кетма-кетликда 8 билан ўзаро туб чегирмалар сони ф (3) дир. ф (8) эса 8 мо- дуль бўйича тузилган чегирмаларнинг келтирилган сио темасидаги чегирмалар сонидан иборат. Демак, ср(8) = °=<|> (8).
Мисол. 19 модуль бўйича 4 сони тегишли бўлган кўрсаткични топинг ва 19 модуль бўйича кўрсаткичга тегишли бўлган чегирмаларнинг келтирилган система- снни тузинг.

Аввало, бевосита ҳисоблаш усули билан 4 сони 19 модуль бўйича қайси кўрсаткичга тегишли эканини то- памиз. 4 нинг барча даражаларини текшириб ўтирмай, унинг фақат 1, 2, 3, 6, 9, 18 даражаларини текширамиз (33- §, 4- натижа).

= 4 (mod 19), 4² = 16 (mod 19), 4³ = 7 ( mod 19),.
4⁶ = 11 (mod 19), 4⁹E= I (mod 19).
Демак, 4 сон 19 модуль бўйича 9 кўрсаткичга тегиш- ли экан.
Энди 19 модуль бўйича кўрсаткичга тегишли бўл- гам сонларни излаймиз. Леммага асосап бундай сонлар сони ср(9) =6 та. 1, 2, 4, 5, 7, 8 система 9 модуль бўйи- ча чегирмаларнинг келтирилган системасидан иборат- дир.

Демак, биз излаган сонлар 4, 4-, 4⁴, 4⁵, 4⁷, 4⁸ лар бў- лади. Бу сонларнн 19 кодуль бўйича энг кичик мус- бат чегирмалар билан алмаштирамиз ва уларни ўсиш тартибида ёзиб, 4,5,6, 9, 16, 17 системага эга бўламиз.

T е о р е м а. р туб модуль бўйича тузилган р – 1 соннииг ҳар бир 8 бўлувчнси <р (8) та синфнннг кўр- сатгичи бўлади. Kycycuii ҳолда 1) tna бошлан- ғин илдизлар синфи мавжуд.


Исботи, Фараз қилайлак B₁₅S₂ 8^ лар р – 1
никг бўлувчилари бўлсин. р модуль бўйича тузилган 1,'2, 3, . . . , р – 1 чегирмалар келтирилган системаси- нинг барча элементларини шу сонларнинг ҳар бири тегишли бўлган кўрсаткичлар бўйича гуруҳларга ажра-
тиб чиқамиз. У ҳолда S₁ га тегишли сонлар сони ф (S₁); $■( га тегишли сонлар сони <|> (S₂) ва ниҳоят B_ft га тегиш- лн сонлар сони ф (B_ft) бўлади. Барча гуруҳларга тақсим- ланган чегирмалар сони р – 1 та бўлгани учун

Ф (8.) + * (^) +... +Ф (h) = P-1 (3)

бўлади.
Иккинчи томондан 25-§ да кўриб ўтганимиздек, бирор соннинг бўлувчилари бўйича тузилган Эйлер функцияларининг йиғиндиси V ср (S_i) =P - 1 (4)
эди. Демак,
•Леммага асосан
Ф (B_i) = ср (B_i) (0)
тенгликка эга бўламиз. Лекин ф(8_г) сон р модуль бў- йича 8_г кўрсаткичга тегишли бўлган чегирмалар сони эди. (6) га асосан ф(З_г) ларнинг сони Ip(S_i) экан.
Хусусий ҳолда, B_ft = /?–1 бўлса, у ҳолда р– 1 кўр- «саткичга тегишли сон бошланғич илдиз бўлади. Демак, р туб модуль бўйича 1) та бошланғич илдизлар синфи мавжуд экан.
Бошланғич илдизлар фақатгина m = 2,4, р^а ва 2/?^а, сонлар учунгина мавжуддир (бу ерда р – тоқ туб coh_s а > 1 натурал сон).

Бошланғич илдизлар бевосита ҳисоблаш усули би- лан топилади. Ҳозирги кунгача уларни топишга ёрдам берувчи бирорта алгоритм ишлаб чиқилмаган.

35-§. Индекслар ва уларнинг хоссалари.

Биз 33- § да ҳар қандай р туб модуль бўйича бош- ланғич илдиз мавжудлигини кўрсатган эдик. Маълум- ки, g сон р модуль бўйича бошланғич илдиз бўлса,
g°, g\ g\ ■ ■ • , g^P~² (I)
сонлар қатори шу р модуль бўйича чегирмаларнинг келтирилган системасини ташкил қилади. (1) қаторнинг
ҳадлари р билан ўзаро туб бўлиб, улар р модуль бўйича <9(р)–р – 1 та синфнинг вакилларидан иборатдир.
Демак, (а;/?)=■ 1 бўлса, у ҳолда (1) қаторда р мо- дуль бўйича а сон билан таққосланувчи ягона элемент топилади, яъни
^а = g^fmod/O) (2)

таққослама ўринли бўлади.

Таъриф. Aгap g сон р туб модуль бўйича бош- ланғич илдиз бўлиб, (а\р)– \ бўлганда (2) таққослама ўринли бўлса, '( > 0 сон а соннинг р модуль бўйича g acocгa нксбаган индекси дейиладн ва у 7 = imi._g а каби белгиланади.
Aгap асос аввалдан берилган бўлса, а нинг индекси Ind а орқали белгиланади.
Бу таърифдан фойдаланиб (2) нн қуйидагича ёзпш мумкин:
_а = g-^ind<2(_m0d₍£»). (3)

Юқоридагиларга асосан, ҳар бир (а\ р)~ 1 шартни қа- ноатлантирувчи а сон берилган g асос бўйича

0,1,2 р- 2 (4)
срнлариинг биттаси билан а!иқланувчи индексга эга экан. Асоснинг ўзгариши билан иидекс ҳам ўзгарадп.
Масалан, 7 модуль бўйича 1,2,3,4,5,6 сонлари ва
улар билан, шу 7 модуль бўйича таққосланувчи барча сонлар 3 асосга кўра
3° = 1 (mod 7), З² = 2 (mod 7), 3 = 3 (mod 7),
3⁴=4(mod7), 3⁶=(mod 7),
3³= – 1 (mod7)
бўлгани учун мос равишда 0, 2, 1, 4, 5, 3 каби ин- дексларга эга. Энди асос а – 5 бўлсин. У ҳолда асос бўйича тузилган индекслар 33- § даги мисолнинг в) сига асосан мос равишда 0, 4, 5, 2, 1, 3 сонларга тенг.
g сон р модуль бўйича бошланғич илдиз бўлгани учун, бошланғич илдизнинг таъ ифига асосан
g^P-=l (mod^) (5)
таққослама ўринли бўлади. Бу таққосламанинг иккала қисмини /г>1) даражаға кўгариб
\=g’^l(p~^y' (mod/^) (6)
га эга бўламиз Энди (2) ва (6) таққосламаларни ҳад-
лаб кўпайтириб,
a~-g¹⁺'^i{p~^l)(modp) (7)
таққосламага эга бўламиз.
(7) таққослама эса ҳар бир (а\ р) = 1 шартни қа-
ноатлантирувчи а сони g бошланғич илдиз бўйича чек-
сиз кўп индексга эга эканини кўрсатади. Бу индекс-
ларнинг барчаси
g+=g-^T,(mod р) (8)
таққосламани қаноаглантиради. (8) нинг ўринли бўлиши учун
Tsrifmod_lP-I) (9)
таққосламанинг бажарилиши зарур ва етарли. Демак,
P модуль бўйича тузилган ва р билан ўзаро туб бўл-
ган ҳар бир синфга (9) таққослама билан аниқланувчи
индекслар тўплами мос келади ва аксинчз.
Бу тушунчаларга кўра (a==b(mo бўлса, у ҳолда
1°. Кўпайтманинг индекси р– 1 модуль бўйича кў« пайтувчилар индексларининг йиғиндиси билан таққос- ланади, яъни
ind{a-b . .. + Indй-f . .. +ind I (mod р – 1).
Исботи. Индекснинг таърифига асосан, қуйидаги таққосламаларғга ёзиб оламиз:
Буларми ҳадлаб кўпайтирамиз. У ҳолда
таққослама ҳосил бўлади. Бундан (2) ва (12) га асосан

2°. Натурал кўрсагкичли даражанинг индекси р–1 модуль бўйича асос индекси ва даража кўрсаткнчипинг кўпайтмаси билан таққосланади, яъни

Исботи. Фараз килайлик, a=b – ..,=l бўлсин. У ҳолда 1-xoccaгa асосан

ind (а-а .. . а) = inda + inda + . .. +
ёки

ҳосил бўлади.

3°. р ихтиёрий туб сон бўлганда р модуль бўйича 1 нинг индекси нолга, асос g нинг индекси эса 1 га тенг бўлади.

Ҳақиқатан, g°=l!modp) ва g'ssg^modp) бўлгани- дан Indl=Ofmodp-1) ва Indg=Iimodp-I) дир. Демак,, индекслар ҳам логарифмлар каби хоссаларга эга экан.

86-§. Индекслар жадвали

Логарифмик жадваллар мавжуд бўлганидек, ихти- ёрий р туб модуль бўйича индекслар жадвалини ту- зиш мумкин. Индексларнинг асоси қилиб р соннинг бирорта бошланғич илдизи олинади. Дастлабки индекс- лар жадвалини рус математиги М. В. Остроградский тузган. У 1837 йилда 200 гача бўлган туб модуллар- учун индекслар жадвалини тузди. Ҳозирги кунда бундай жадваллар 10000 гача туб модуллар учун ту- зилган.
Ҳар бир жадвал қуйидаги 2 та қисмдан иборат бў- лади:
берилган п сон бўйича / индексни топиш}
берилган / индекс бўйича п сонни топиш.
Бирор р модуль бўйича индекслар жадвалини тузиш учун аввало р модуль бўйича g бошланғич илдизни топиш лозим. Сўнгра
g°, g¹,..., g^p~²

даражалар р модуль бўйича энг кичик мусбат чегир» маларга алмаштирилади. Масалан, р=11 модуль бў- йича индекслар ва уларга мос сонлар жадвалини ту- зайлик. Бевосита ҳисоблаш усули билан 2, 6, 7, 8 лар

11 модуль бўйича бошланғич илдиз эканига ишонч ҳосил қиламиз.
Ҳақиқатан, <р( 11) = 10 бўлгани учун
2=2(modll), 2³=8{modll),
2⁴=5(mod 11), 2*=4(mod 11),
2⁵sl0(modl 1), 2¹⁰=1( mod i 1),
2⁹=6(mod 11), 2^e=9(mod 11),
2⁷=7(modll), 2⁸=3(modll) ларга асосан 2 бошланғнч илдиздир.
6=6(modll), 6³=7(modll), 6¹⁰=I (mod 11),
6²=3(mod 11), 6⁵=10{mod 11).
Демак, Il модуль бўйича б ҳам бошланғич илдиз экан.

Энди асос2бўлгаида қуйидаги жадвалларни тузамиз:

п	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

Биринчи жадвалга асосан, сон берилса, индекс то- пилади, иккинчи жадвалга асосан эса индексга қараб сон топилади.
^ = 43 модуль бўйича 3, 5, 12, 18, 19, 20, 26, 28, 30, 33, 34 сонлар бошланғич илдиздир. g–28 бўлганда қуйидаги жадвалларга эга бўламиз:
Бу жадваллардаги сатрлар ва усгунлар мос равиш- да сон (индекс) нинг ўнлик ва бирлик хонасини бил- дириб, уларнинг кесишган жойида изланаётган индекс (сон) туради.
Мисол. 43 модуль бўйича 37 соннинг индексини юпинг.
Биринчи жадвалдаги 3-сатр ва 7-устуннинг кесишган жойида ЗБсони жойлашган. Де.мак, ind₂₈37=35. Энди ак- синча 43 модуль бўйича индекси 18 га тенг сонми топинг.

Иккинчи жадвалга асосан биринчи сатр ва 8- устуннинг

кесишган жойига 41 сони мос келади. Демак, «=41.
Aгap изланаётган сон (ёки индекс) >i>адвалдаги энг катта сондан ҳам катта бўлса, бу сон қаралаётган р ёки р– I модуль бўйича энг кичик мусбат чегирма билан алмаштириб олинади.
Бошланғич илдизи мавжуд бўлган ҳар қандай мо- дуль бўйича индекслар жадвалини тузиш мумкии. Чунки бундай ҳолда ҳам бошланғич илдизнинг даража- лари m модуль бўйича чегирмаларнинг келтирилган системасини ташкил қиладя.
Тацқосламалар назариясининг арифметикага
татбиқлари
I. Бўлиниш аломатлари. Бутун сонлар тўп- ламига тегишли ихтиёрий а ва /;г>O сонлари берилган бўлсин. Кўп ҳолларда & сонни m сонга бўлишдан ҳо- сил бўлган энг кичик қолдиқни топиш талаб этилади. Бу масалани ҳа-л этишнинг умумлашган усулини даст- лаб француз математиги Б. Паскаль кўрсатган эди.
37-§. Индекслар ёрдамида гаққосламаларни
ечиш
Индексларнинг хоесаларидан фойдаланиб, икки хадли таққосламаларни осонгина ечиш мумкин. Бундай мисолларни ечиш учун берилган сон бўйича унинг индексини .(маълум асосга кўра) ва аксинча
келади. Шунинг учун мазкур қўлланманинг охирида 1 дан 103 гача туб сонларнинг индекслари жадвали келтирилган.
Фараз қилайлик,
ал^п=Ь{тоАр) (1)

таққослама берилган бўлиб, (а\ р) = 1 ва р тоқ туб сон бўлсин. Индекслар тушунчасидан фойдаланиб, (1) ни унга тенг кучли

таққослама билан алмаштирамиз. Энди, ind х ни но* деаълум сифатида қараҳ (2) таққосламани ечамиз. Aгap бу таққослама умуман ечимга эга бўлса, қуйидапг икки ҳолдан бири бўлиши мумкин:

Aгap 1-ҳол урйнли бўлса, 27-§ га асосан (2) тақ- ,қослама ind га ниоатан ягона ечимга эга бўлади.

Aгap ind х–с ечим бўлса, индекслар жадвалидан фойдаланиб, х ни топамиз. х нинг топилган қиймаш р модуль бўйича берилган тацқосламанинг ечими бўлади.
2-ҳол ўринли бўлсин, яъни р– l)=d>l бўлсин. Унда қуйидаги 2 та ҳол юз беради:
а) (indА–тйа)ХЛ, яъни ind6–inda сон d га бў- линмайди. Бундай ҳолда такқосламаларнинг хоссасига асосан (2) ечимга эга бўлмайди.

1. 
   ва (2) тенг кучли бўлгани учун (1) ҳам ечим- га эга бўлмайди.
   

б) (ind b–ind a)yd, яъни indb– ind а сон d га бўлйн- ¹ син. У ҳолда (2) таққосламани қуйидагича ёзиш мум- кин:
Бунла ^M=-I бўлгани учун охирги таққослама
- модуль бўйича фақат битта ечимга эга бўлади. D Яна (2) таққослама р– 1 модуль бўйича d та ечимга ҳам эга бўлади. Бу ечимларни ind х лар бўйича топиб, индехслар жадвали ёрдамида зса (1) нинг ечимларини топамиз.

Индекслар одатда бирор бошланғич илдизга нисба- тан тузилгани учун ҳар бир таққослама ечммини ал- батта дастлаб берилган модуль бўйича топиш керак. Чунки биз бошланғич илдизлар ўзгариши билан ин- декслар ҳам ўзгаришини кўриб ўтган эдик.

1-мисол. x^b=14(mod41) таққосламани ечинг.
Бу таққосламанинг иккала қисмини индекелаймиз. У ҳолда
ind x=ind 14(mod40_).
Жадвалга асосан, ind 14==25. Демак, 5 ind к=25(mod 40) ёки ind x=5(mod 8).
(5;4Э)=5 бўлгани учун берилган тақцослама 41 мо- дуль буйича 5 та ечимга эга булади. У ечимлар
ind X₁=Slmod 40), ind x_v=13(mod 40), ind X₃=-1
(mod40),
ind x₄=29,mod 40), ind x_b=37(mod 40)
таққосламалараан индекслар бўйича

x,=27(mod 41), x>=24(mod 41), x₃=35(mod 41),

x₄=22(mod 41), x₆=15^fmod 41).

Энди x"=a(mod p) таққосламанинг ечилиш шартини кўрсатамиз.
Бу таққосламанинг ечилиш шаргини келтириб чи- қариш учун унинг иккала қисмики индекслаб,
п ind x=ind a(modр–I) (4)
таққосламага эга бўламиз.
(n\p–\)=d бўлганда охирги такқосламанинг ечимга эга бўлиши учун inda нинг d га бўлиниши зарур ва етарлидир, яъни
inda=0(modc7) (5)
бажарилиши керак. (5) ни р ва d лар орасидаги боғланиш орқали ифодалайлик. Бунинг учун (5) нинг иккала қисмини ва модулини га кўпайтирамиз. У ҳолда (5) таққослама билан тенг кучли бўлган inda≡0(mod p-1) таққослама ҳосил бўлади. Индекслар тушунчасидан фойдаланиб, бу таққосламани

кўринишда ёзамиз. 0≡ ind l (mod р-1) бўлганидан ва юқоридаги таққосламага мувофиқ қуйидагини ёза оламиз:

Ҳосил бўлган (6) таққослама (3) таққосламанинг ечилиш шарти. (6) да п=2 бўлганда бизда маълум бўлган Эйлер шарти келиб чиқади. Ҳақиқатан, бундай ҳолда р ток туб сон бўлгани учун d = (2; р–1) = 2, яъни d=2 бўлиб, (6) таққослама

кўринишни олади. Бу эса х²≡а (mоd р) таққосламанинг ечилиш шарти эди.
Ушбу
а^х ≡ b (mоd р) (7)
кўринишдаги таққослама кўрсаткичли таққослама дейилади. Бу таққосламани ечиш учун унинг ҳар иккала қисмини индекслаб,
х inda ≡ ind b (mod р–1) (8)
таққосламани ҳосил қиламиз. Бу таққослама эса биринчи даражали бир номаълумли таққослaма бўлиб, бундай таққосламаларни ечишни 23-мавзуда кўриб ўтган эдик.