Eyler funksiyasi. Eyler va Ferma teoremalari

Eyler teoremasidan foydalanish usuli. Ma`lumki, <sup>(</sup>𝑎, 𝑚<sup>)</sup> = 1 bo`lsa, u holda 𝑎^𝜑(𝑚) ≡ 1 (𝑚𝑜𝑑𝑚) taqqoslama o`rinli edi. Shunga ko`ra, 𝑥 = 𝑎^{𝜑(𝑚)−1} ∙
𝑏(𝑚𝑜𝑑𝑚) bo`ladi.
Misol. 3𝑥 ≡ 7<sup>(</sup>𝑚𝑜𝑑11<sup>)</sup>
𝑥 ≡ 3<sup>𝜑(11)−1</sup> ∙ 7<sup>(</sup>𝑚𝑜𝑑11<sup>)</sup> 𝜑<sup>(</sup>11<sup>)</sup> = 10
𝑥 ≡ 3<sup>9</sup> ∙ 7<sup>(</sup>𝑚𝑜𝑑11<sup>)</sup> ≡ <sup>(</sup>3<sup>3)3</sup> ∙ 7 ≡ 5<sup>3</sup> ∙ 7 ≡ 4 ∙ 7 ≡
28 ≡ 6(𝑚𝑜𝑑11)
Taqqoslamaning moduli yetarlicha katta bo`lsa, quidagi usul ancha qulaydir.
Uzluksiz kasrlardan foydalanish usuli.
𝑎𝑥 ≡ 𝑏(𝑚𝑜𝑑𝑚)

taqqoslama berilgan bo`lib, <sup>(</sup>𝑎, 𝑚<sup>)</sup> = 1 ∧ 𝑎 > 0 bo`lsin. ^𝑚
𝑎
kasrni uzluksiz

kasrlarga yoyib, uning munosib kasrlarini ^𝑃𝑘
𝑄_𝑘
(𝑘 = ^̅1^̅̅,^̅𝑛^̅) kabi belgilaymiz, bunda

𝑃_𝑛 = 𝑚 ∧ 𝑄_𝑛 = 𝑎 bo`ladi, u holda

𝑃_𝑛𝑄_𝑛−1 − 𝑃_𝑛−1𝑄_𝑛 = (−1)^𝑛

tenglikni

𝑚𝑄_𝑛−1 − 𝑎𝑃_𝑛−1 = ⁽−1^)𝑛

ko`rinishda yozish mumkin, yoki

𝑎𝑃_𝑛−1 ≡ ⁽−1^)𝑛 + 𝑚𝑄_𝑛−1 dan
𝑎𝑃_𝑛−1 ≡ ⁽−1^)𝑛−1(𝑚𝑜𝑑𝑚⁾ (2)
(2) ni (−1)^𝑛−1 ∙ 𝑏 ga ko`paytirib,
(−1)^𝑛−1 ∙ 𝑏 ∙ 𝑎𝑃_𝑛−1 ≡ 𝑏(𝑚𝑜𝑑𝑚) (3)
(1) va (3) ni solishtirib

𝑥 ≡ ⁽−1^)𝑛−1𝑏 ∙ 𝑃_𝑛−1(𝑚𝑜𝑑𝑚)

𝑎
ni hosil qilamiz. Bu erda 𝑃_𝑛−1 son ^𝑚
kasrning ⁽𝑛 − 1⁾ − munosib kasrning

suratidan iborat.

1. 
   taqqoslama yagona yechimga ega bo`lgani uchun (3) yechim (1) ning yagona yechimi bo`ladi.
   

MISOL. 68𝑥 ≡ 164(𝑚𝑜𝑑212)


⁽68,164⁾ = 4, 212/4
17𝑥 ≡ 41⁽𝑚𝑜𝑑53⁾, ⁽17,53⁾ = 1
𝑃_𝑘−1 = 25 𝑛 = 3, 𝑛 − 1 = 2
𝑥₀ ≡ ⁽−1⁾² ∙ 25 ∙ 41⁽𝑚𝑜𝑑53⁾ ≡ 18⁽𝑚𝑜𝑑53⁾
𝑥 ≡ 18, 71, 124, 177(𝑚𝑜𝑑212)

Ljandr simvoli va uning xossalari.

Ushbu 𝑥² ≡ 𝑎 ⁽𝑚𝑜𝑑 𝑝⁾ , ⁽𝑎; 𝑝⁾ = −1 taqqoslamaning moduli yetarlicha katta bo’lganda Eyler kriteriysidan foydalaninsh unchalik qulay emas. Bunda
hollarda Lejandr simvoli deb ataluvchi va (^𝑎) kabi atluvchi simvoldan
𝑝
foydalaniladi.


Ta’rif. Quyidagi shatrlarniqanoatlantiruvchi (^𝑎) simvol Lejandr simvoli
𝑝
deyiladi:


𝑎 (_𝑝)

= {
1, 𝑎𝑔𝑎𝑟 𝑎 𝑠𝑜𝑛 𝑝 𝑡𝑜𝑞 𝑡𝑢𝑏 𝑚𝑜𝑑𝑢𝑙 𝑏𝑜^′𝑦𝑖𝑐ℎ𝑎𝑘𝑣𝑎𝑑𝑟𝑎𝑡𝑖𝑘 𝑐ℎ𝑒𝑔𝑖𝑟𝑚𝑎 𝑏𝑜^′𝑙𝑠𝑎;
−1, 𝑎𝑔𝑎𝑟 𝑎 𝑠𝑜𝑛 𝑝 𝑡𝑜𝑞 𝑡𝑢𝑏 𝑚𝑜𝑑𝑢𝑙 𝑏𝑜^′𝑦𝑖𝑐ℎ𝑎𝑘𝑣𝑎𝑑𝑟𝑎𝑡𝑖𝑘 𝑐ℎ𝑒𝑔𝑖𝑟𝑚𝑎𝑚𝑎𝑠 𝑏𝑜^′𝑙𝑠𝑎.


(^𝑎) simvol a sondan p bo’yicha tuzlgan Lejandr simvoli deb taladi, bu yerda a
𝑝
Lejandr simbolining surati, p esa Lejandr simvolining maxraji deyiladi.

Misol. ( ⁷ ) = 𝟏, chunki Eyler kriteriysiga asosan, 7
19
19−1
² ≡ 1 (𝑚𝑜𝑑 19)

bo’lgani uchun 7 son 19 modul bo’yicha vadratik chegirmadir. 5 son 17 modul
bo’yicha kvadratik chegirmamas bo’lganligidan ( ⁵ ) = −1 bo’ladi.
17

Ma’lumki, 𝑎

𝑝−1
² ≡ 1 (𝑚𝑜𝑑 𝑝) , 𝑎

𝑝−1
² ≡ −1 (𝑚𝑜𝑑 𝑝) ekanligiga qarab, a

kvadratik chegirma yoki kvadratik chegirmamas bo’ladi. Demak, Ljandr simvoli va Eyler kriteriylariga asosan, quyidagini yoza olamiz:

₍𝑎
𝑝

) ≡ 𝑎

𝑝−1
² (𝑚𝑜𝑑 𝑝). (1)

Endi Lejandr simvolining quyidagi ba’zi bir xossalarini o’rib chiqamiz:

1-xossa. 𝑎 ≡ 𝑎₁⁽𝑚𝑜𝑑 𝑝⁾ => (^𝑎) = (^𝑎1) . (2)
𝑝 𝑝

Haqiqatan, bitta sinfning elementlari berilgan modul bo’yicha yo kvadratik chegirma, yoki kvadratik chegirmamas bo’ladi. Bunga asosan, (1) ning to’g’rilii kelib chiqadi. Bu xossadan foydalanib, har qanday 𝑘 ∈ 𝑍 uhun quyidagini yoza

olamiz: (^𝑎) = (^{𝑘𝑝+𝑎1}), (^{𝑘𝑝+𝑎1}) = (^𝑎1) bo’lgani uchun (^𝑎) = (^𝑎1) bo’ladi.
𝑝 𝑝 𝑝 𝑝 𝑝 𝑝


2-xossa. (¹) = 1 .
𝑝

Haqiqatan, 𝑥² ≡ 1 (𝑚𝑜𝑑 𝑝) taqqoslama doimo yechimga ega bo’lib, 𝑥 ≡
±1 ⁽𝑚𝑜𝑑 𝑝⁾ uning yehimidir.

3-xossa. (⁻¹) = (−1)
𝑝
𝑝−1
2 _.

1. 
   taqqoslamaga asosan quyidagini yoza olamiz:
   

₋₁ 𝑝−1
( _𝑝 ) = (−1) ² (𝑚𝑜𝑑 𝑝) (3).


₋₁ 𝑝−1
Lekin ( _𝑝 ) va (−1) ² larning qiymati ±1 dan farqli emas. Shu bilan bir
vaqtda p toq tub son bo’lgani uchun 1 va -1 lar shu modul bo’yicha taqqoslanuvchi
₋₁ 𝑝−1

bo’la olmaydi. Demak, ( _𝑝 ) va (−1)
bo’ladi.


4-xossa. (^𝑎∙𝑏) ≡ (^𝑎) ∙ (^𝑏) .
² lar bir vaqtda 1 ga yoki -1 ga teng

𝑝 𝑝 𝑝


Isboti. (1) taqqoslaamaga asosan quyidagini yozish mumkin: (^𝑎∙𝑏) ≡
𝑝

𝑝−1

𝑝−1

𝑝−1

𝑎 𝑏
𝑎∙𝑏 𝑎

⁽𝑎 ∙ 𝑏⁾
𝑏
² ≡ ⁽𝑎^)
2 ∙ ⁽𝑏⁾
𝑝−1


² ≡ (
𝑝
𝑝−1

) ∙ (
𝑝

𝑎
) (𝑚𝑜𝑑 𝑝) yoki ( _𝑝
𝑏
) ≡ ( ) ∙
𝑝

( ) (𝑚𝑜𝑑 𝑝) . ⁽𝑎⁾
𝑝
² ∙ ⁽𝑏^)
2 ≡ (
𝑝
) ∙ (_𝑝
) ⁽𝑚𝑜𝑑 𝑝⁾ taqqoslamaning ikkala qismi

a va b lar p modul bo’yicha kvadratik chegirma yoki kvadratik chegirmamas bo’lsa, 1 ga, a va b larning biri p modul bo’yicha kvadratik chegirma, ikkinchisi
esa kvadratik chegirmamas bo’lsa, -1 ga teng. Shuning uchun (^𝑎∙𝑏) ≡ (^𝑎) ∙ (^𝑏)

𝑝
tenglikni yosa olamiz. Bu xossadan quyidagi natijalar kelib chiqadi:
1-natija. (^𝑎2) ≡ 1, (^𝑎∙𝑏2) ≡ (^𝑎) .
𝑝 𝑝

𝑝 𝑝 𝑝


2-natija. Juft sondagi kvadratik chegirmalar yoki kvadratik chegirmamaslar ko’paytmasi doimo kvadratik chegirma bo’ladi. Toq sondagi kvadratik chegirmamaslar ko’paytmasi yana kvadratik chegirmamas bo’ladi.
₂ 𝑝²−1

5. 
   xossa. (
   

𝑝
) ≡ (−1) ⁸ .

Biz bu xossani isbot qilib o’tirmasdan undan amaliy mashg’ulotlarda foydalnishning a’zi bir tomonlarin ko’rsatib o’tamiz.

1. 
   𝑝 ≡ 8𝑚 ± 1 shakldagi tub son bo’lsin. U holda
   

𝑝² − 1
₈ =
(8𝑚 ± 1)² − 1
₈ = 8𝑚²

± 2𝑚 ≡ 0 (𝑚𝑜𝑑 2)

Bo’lgani uchun (²) ≡ 1.
𝑝

2. 
   𝑝 ≡ 8𝑚 ± 3 shakldagi tub son bo’lsa,
   

𝑝² − 1
₈ =
(8𝑚 ± 3)² − 1
₈ = 8𝑚²

± 6𝑚 + 1 ≡ 1 (𝑚𝑜𝑑 2)

bo’adi. Demak, 𝑝 ≡ 8𝑚 ± 3 shakldagi tub son bo’lsa, 2 son p modul boyicha kvadratik chegirmamas bo’lad, ya’ni (²) ≡ −1.
𝑝

5. 
   xossa. O’zarolik qonuni.
   

Agar p va q lar har xil toq tub son bo’lsa,

𝑝 𝑞
𝑝−1_∙𝑞−1

tenglik o’rinli bo’ladi.

( ) ∙ (
𝑞 𝑝
) ≡ (−1) ^{2 2} (4)

Bu xossani ham isbot qilmasan uning amaliy mashg’ulotlardaqo’llanishini

ko’rsatmiz. Buning uchun (4) ning har ikkaa qismini (^𝑝 ) ga ko’paytiramiz:
𝑞


_𝑞 𝑝−1_∙𝑞−1 _𝑝

bu yerda


₍𝑝
𝑞
2
) = 1.
( ) ≡ (−1) ²
𝑝
² ( ), (5)
𝑞

(5) tenglikka asosan, p va q larning kamida bittasi 4m+1 shakldagi son bo’lsa,

𝑝−1_∙𝑞−1

𝑝 𝑞

(−1) ^2
2 = 1 bo’lib, (
𝑞
) = (
𝑝
) hosil boladi.

Agar p va q larning har biri 4m+3 shaklagi tub son bo’lsa,u holda (-1) ning

darajasi toq son bo’lib, (^𝑝) = − (^𝑞) bo’ladi.
𝑞 𝑝


Misol. 𝑥² ≡ 426(𝑚𝑜𝑑 491) taqqoslama yechimga egami?


Bu savolga javob berish uchun (⁴²⁶) Lejandr simvolini tuzamiz. 426 = 2 ∙
491
3 ∙ 71 shakldagi son bo’lgani uchun 4- xossaga asosan quyidagicha yozamiz:

₍426_{) ≡ (} 2
) ∙ ( ³
) ∙ ( ⁷¹ ) .

491
491
491
491

1. ( ²
491
2. ( ³
) ≡ −1, chunki 491 ≡ 3 (𝑚𝑜𝑑 8).
) ≡ − (⁴⁹¹) ≡ − (²) ≡ −⁽−1⁾ = 1, chunki 491 ≡ 3 (𝑚𝑜𝑑 4) va 3 ≡

491 3 3
3 (𝑚𝑜𝑑 4) hamda 3 ≡ 3 (𝑚𝑜𝑑 8).
3. ( ⁷¹ ) ≡ − (⁴⁹¹) ≡ − (⁶⁵) ≡ − ( ⁵ ) ∙ (¹³) ≡ − (⁷¹) ∙ (⁷¹) ≡ − (¹) ∙ ( ⁶ ) ≡

491
71 71
71 71
5 13
5 13

− ( ² ) ∙ ( ³ ) ≡ −⁽−1⁾ (¹³) ≡ 1 ∙ (¹) ≡ 1, chunki 491 ≡ 3⁽𝑚𝑜𝑑 4⁾, 71 ≡
13 13 3 3
3 ⁽𝑚𝑜𝑑 4⁾, 491 ≡ 65 ⁽𝑚𝑜𝑑 71⁾, 5 ≡ 1 ⁽𝑚𝑜𝑑 4⁾, 13 ≡ 5 (𝑚𝑜𝑑 8).


Demak, (⁴²⁶) ≡ ⁽−1⁾ ∙ 1 ∙ 1 = −1, ( ⁴²⁶) ≡ −1 , bo’lgan uchun berilgan

491
taqqoslama yechimga ega emas.
491