TEOREMA. Eyler funksiyasi multiplikativ funksiyadir. TEOREMA

Download 222,9 Kb.
bet	2/4
Sana	14.05.2024
Hajmi	222,9 Kb.
	#233376

1 2 3 4

Bog'liq
Eyler

TEOREMA. Eyler funksiyasi multiplikativ funksiyadir.
TEOREMA. Eyler funksiyasi multiplikativ funksiyadir.
ISBOTI. a va b o`zaro tub bo`lgan musbat butun sonlar bo`lsin. 𝑎 ∙ 𝑏 dan kichik bo`lgan barcha manfiymas sonlar to`plami M ni qaraylik. M dagi har bir sonni, qoldiqli bo`lish teoremasiga asosan, yagona tarzda
𝑏 ∙ 𝑞 + 𝑟 (𝑟 ∈ ^{0,1, … , 𝑏 − 1^}, 𝑞 ∈ ^{0,1,2, … , 𝑎 − 1^})
ko’rinishda ifodalash mumkin.
𝑏𝑞 + 𝑟 son a bilan o`zaro tub bo`lishi uchun ⁽𝑏, 𝑟⁾= 1 bo`lishi zarur va yetarli. Bunday 𝑟 sonlar soni 𝜑(𝑏) ta bo`ladi. 𝑟₁ −shunday sonlarning biri bo`lsin. U holda
𝑟₁, 𝑏 + 𝑟₁, 2𝑏 + 𝑟₁, … , 𝑏⁽𝑎 − 1⁾+ 𝑟₁
sonlar ketma-ketligi a modul bo`yicha chegirmalarning to`la sistemasini tashkil etadi. Shuning uchun, bu sonlar orasida a bilan o`zaro tub bo`lgan sonlar 𝜑(𝑎) ta bo`ladi. Shunday qilib, har bir 𝑟₁ songa (𝑏 bilan o`zaro tub bo`lgan) 𝑏𝑞 + 𝑟₁ ko`rinishdagi a bilan o`zaro tub sonlar va demak, ab bilan ham o`zaro tub bo`lgan
𝜑(𝑎) ta son mos keladi. Shuning uchun, ab bilan o`zaro tub bo`lgan sonlar soni
𝜑(𝑎) ∙ 𝜑(𝑏), ya`ni
𝜑⁽𝑎𝑏⁾= 𝜑(𝑎) ∙ 𝜑(𝑏)
bo`ladi.
TEOREMA. Agar 𝑚 = 𝑝₁^𝛼¹∙ 𝑝₂^𝛼²∙ … ∙ 𝑝_𝑛^𝛼^𝑛bo`lsa, u holda

bo`ladi.
𝜑⁽𝑚⁾= 𝑚 (1 −
1

𝑝₁
) (1 −
1

𝑝₂
) ∙ … ∙ (1 −
1
)
𝑝_𝑛

ISBOTI. 𝜑(𝑚) funksiya mul`tiplikativ bo`lgani uchun, bu funksiyani

𝑘
𝜑(𝑝^𝛼𝑘) uchun hisoblashni bilish kifoya.
𝑝^𝛼 dan kichik manfiy bo`lmagan va 𝑝^𝛼 bilan o`zaro tub bo`lmagan sonlar sonlar soni 𝑝^𝛼−1 ga teng, chunki faqat 𝑘𝑝, 0 ≤ 𝑘 < 𝑝^𝛼−1 sonlargina 𝑝^𝛼 bilan o`zaro tub bo`lmaydi. Shuning uchun 𝑝^𝛼 dan kichik va 𝑝^𝛼 bilan o`zaro tub sonlar soni

_𝑝𝛼 ₋_𝑝𝛼−1

ta bo`ladi.

𝜑⁽𝑝^𝛼⁾
= 𝑝^𝑎
1
(1 − )
𝑝

𝑚 = 𝑝 ^𝛼¹∙ 𝑝^𝛼2 ∙ … ∙ 𝑝^𝛼𝑛 va 𝜑 multiplikativ bo`lgani uchun
¹2 ^𝑛
𝜑⁽𝑚⁾= 𝜑(𝑝^𝛼1) ∙ 𝜑(𝑝^𝛼2) ∙ … ∙ 𝜑(𝑝^𝛼𝑛)
1 2 ^𝑛
= 𝑝^𝛼1 (1 − ¹) ∙ 𝑝^𝛼2 (1 − ¹) … 𝑝^𝛼𝑛 (1 − ¹)

1 _𝑝₁2

_𝑝₂𝑛

𝑝_𝑛

= 𝑝 ^𝛼¹∙ 𝑝^𝛼2 ∙ … ∙ 𝑝^𝛼𝑛 (1 − ¹) (1 − ¹) ∙ … ∙ (1 − ¹)

¹2 ^𝑛

2
1 1

𝑝₁

𝑝₂
1

𝑝_𝑛

1
= 𝑚 (1 − _𝑝
) (1 − _𝑝
) ∙ … ∙ (1 − )

𝑝
𝑛

EYLER TEOREMASI. Agar a butun son 𝑚 bilan o`zaro tub bo`lsa, u holda
𝑎^𝜑(𝑚) = 1(𝑚𝑜𝑑𝑚) (1)
bo`ladi.
ISBOTI. 𝑎₁, 𝑎₂, … , 𝑎_𝜑(𝑚)(2) - m modul bo`yicha chegirmalarning keltirilgan sistemasi bo`lsin, u holda 2-teoremaga ko`ra,
𝑎𝑎₁, 𝑎𝑎₂, … , 𝑎𝑎_𝜑(𝑚)(3)
ham m modul` bo`yicha chegirmalarning keltirilgan sistemasi bo`ladi. Shuning uchun (3) sonlar ko`paytmasi (2) sonlar ko`paytmasi bilan m modul` bo`yicha taqqoslanadi, ya`ni
𝑎^𝜑(𝑚)𝑎₁∙ 𝑎₂∙ … ∙ 𝑎_𝜑₍_𝑚₎≡ 𝑎₁∙ 𝑎₂∙ … ∙ 𝑎_𝜑₍_𝑚₎(𝑚𝑜𝑑𝑚)
𝑎₁𝑎₂∙ … ∙ 𝑎_𝜑(𝑚)ko`paytma 𝑚 bilan o`zaro tub, shuning uchun taqqoslamaning xossasiga ko`ra, 𝑎₁𝑎₂… 𝑎_𝜑₍_𝑚₎ga bo`linishi mumkin, demak,
𝑎^𝜑(𝑚) ≡ 1(𝑚𝑜𝑑𝑚)
bo`ladi.
FERMA TEOREMASI. Agar a son p tub songa bo`linmasa, u holda
𝑎^𝑝−1 ≡ 1(𝑚𝑜𝑑𝑝)

taqqoslama o`rinli bo`ladi.
ISBOTI. a son p tub songa bo`linmasa, u holda ⁽𝑎, 𝑝⁾= 1 bo`ladi. Bundan, Eyler teoremasiga ko`ra, 𝑚 = 𝑝 va 𝜑⁽𝑝⁾= 𝑝 − 1 ekanligidan
𝑎^𝜑(𝑝) ≡ 1(𝑚𝑜𝑑𝑝)
𝑎^𝑝−1 ≡ 1(𝑚𝑜𝑑𝑝)
bo`ladi, yoki ⁽𝑎, 𝑝⁾= 1 bo`lgani uchun
𝑎^𝑝 ≡ 𝑎(𝑚𝑜𝑑𝑝).
Misol 1. Eyler funksiyasini hisoblang: 𝜑⁽18 ∙ 42⁾
Yechish: 18 bilan o’zaro tub bo’lgan musbat sonlar: 1, 5, 7, 11, 13, 17. Demak, 18 bilan o’zaro tub bo’lgan musbat sonlar soni 6 ta; 42 bilan o’zaro tub bo’lgan musbat sonlar: 1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41. Demak, 42 bilan o’zaro tub bo’lgan musbat sonlar soni 12 ta
𝜑⁽𝑎 ∙ 𝑏⁾= 𝜑⁽𝑎⁾∙ 𝜑⁽𝑏⁾ga asosan 𝜑⁽18 ∙ 42⁾= 𝜑⁽18⁾∙ 𝜑⁽42⁾= 6 ∙ 12 = 72, ya’ni 𝜑⁽18 ∙ 42⁾= 72 yechim hosil bo’ladi.
Misol 2. 7𝑥 ≡ 10(𝑚𝑜𝑑 4) taqqoslamani Eyler teoremasi yordamida yeching.
Yechish: 𝑎𝑥 ≡ 𝑏(𝑚𝑜𝑑 𝑚) taqqoslama (a,m)=1 bo’lsa, u hola uning yechimi 𝑥 ≡
𝑏 ∙ 𝑎^{𝜑(𝑚)−1}(𝑚𝑜𝑑 𝑚) formula yordamida topiladi. Haqiqatan ham Eyler teoremasiga ko’ra 𝑎^{𝜑(𝑚)−1} ≡ 1(𝑚𝑜𝑑 𝑚). Bundan 𝑎^𝜑(𝑚)𝑏 ≡ 𝑏(𝑚𝑜𝑑 𝑚) va 𝑎 ∙
𝑎^{𝜑(𝑚)−1}𝑏 ≡ 𝑏(𝑚𝑜𝑑 𝑚) larni hosil qilsak, 𝑥 ≡ 𝑏𝑎^{𝜑(𝑚)−1}(𝑚𝑜𝑑 𝑚) kelib chiqadi.
7𝑥 ≡ 10(𝑚𝑜𝑑 4) dan a=7, b=10, m=4 yechim 𝑥 ≡ 10 ∙ 7^𝜑(4)−1(𝑚𝑜𝑑 4) ni

)
topish uchun 𝜑⁽4⁾ni aniqlaymiz. 4 = 2² ekanligidan 𝜑⁽4⁾= 4 ∙ (1 − ¹= 2
2
kelib chiqadi. Demak, 𝑥 ≡ 10 ∙ 7²⁻¹(𝑚𝑜𝑑 4). Agar 10 ≡ 2 ⁽𝑚𝑜𝑑 4⁾, 7 ≡
3 ⁽𝑚𝑜𝑑 4⁾, 6 ≡ 2 (𝑚𝑜𝑑 4) taqqoslamalaran foydalansak 𝑥 ≡ 10 ∙
7²⁻¹⁽𝑚𝑜𝑑 4⁾= 2 ∙ 3 = 6 ≡ 2 ⁽𝑚𝑜𝑑 4⁾, ya’ni 𝑥 ≡ 2 ⁽𝑚𝑜𝑑 4⁾yechimni hosil qilamiz.

Birinchi darjali taqqoslamalar va ularni yechish usullari.

TA`RIF. Ushbu 𝑎𝑥 ≡ 𝑏(𝑚𝑜𝑑𝑚) (1) ko`rinishdagi taqqoslama bir noma`lumli birinchi darajali taqqoslama deyiladi. (bu erda a va b-butun sonlar, m-natural son)
TA`RIF. Agar (1) taqqoslamada 𝑥 = 𝑥₀ bo`lganda 𝑎𝑥₀ ≡ 𝑏(𝑚𝑜𝑑𝑚)

taqqoslama to`g`ri bo`lsa, u holda 𝑥₀ son taqqoslamani qanoatlantiradi deyiladi.

TA`RIF. 𝑚 modul` bo`yicha taqqoslamaning yechimlar soni deb, bu taqqoslamaning m modul` bo`yicha chegirmalarning to`liq sistemadagi yechimlar soniga aytiladi.

Agar a son (1) taqqoslamani qanoatlantirsa u holda m modul` bo`yicha a bilan taqqoslanuvchi ∀ 𝑏 son ham bu taqqoslamani qanoatlantiradi, bunday 2 ta yechim bitta deb qaraladi.
Misol. 5𝑥 ≡ 3⁽𝑚𝑜𝑑6⁾, 0, 1, 2, 3, 4, 5 𝑥 = 3⁽𝑚𝑜𝑑6⁾𝑥₀ = 3 + 6𝑡, ∀𝑡 ∈ ℤ 𝑥₀ = 9, 15, … sonlar ham bu taqqoslamani qanoatlantiradi.

Download 222,9 Kb.

1 2 3 4

Download 222,9 Kb.