TEOREMA. Eyler funksiyasi multiplikativ funksiyadir.
TEOREMA

|
TEOREMA. Eyler funksiyasi multiplikativ funksiyadir.
TEOREMA
|
bet | 2/4 | Sana | 14.05.2024 | Hajmi | 222,9 Kb. | | #233376 |
Bog'liq EylerTEOREMA. 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. 𝑟1 −shunday sonlarning biri bo`lsin. U holda
𝑟1, 𝑏 + 𝑟1, 2𝑏 + 𝑟1, … , 𝑏(𝑎 − 1) + 𝑟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 𝑟1 songa (𝑏 bilan o`zaro tub bo`lgan) 𝑏𝑞 + 𝑟1 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 𝑚 = 𝑝1𝛼1 ∙ 𝑝2𝛼2 ∙ … ∙ 𝑝𝑛𝛼𝑛 bo`lsa, u holda
bo`ladi.
𝜑(𝑚) = 𝑚 (1 −
1
𝑝1
) (1 −
1
𝑝2
) ∙ … ∙ (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 − )
𝑝
𝑚 = 𝑝 𝛼1 ∙ 𝑝𝛼2 ∙ … ∙ 𝑝𝛼𝑛 va 𝜑 multiplikativ bo`lgani uchun
1 2 𝑛
𝜑(𝑚) = 𝜑(𝑝𝛼1) ∙ 𝜑(𝑝𝛼2) ∙ … ∙ 𝜑(𝑝𝛼𝑛)
1 2 𝑛
= 𝑝𝛼1 (1 − 1 ) ∙ 𝑝𝛼2 (1 − 1 ) … 𝑝𝛼𝑛 (1 − 1 )
1 𝑝1 2
𝑝2 𝑛
𝑝𝑛
= 𝑝 𝛼1 ∙ 𝑝𝛼2 ∙ … ∙ 𝑝𝛼𝑛 (1 − 1 ) (1 − 1 ) ∙ … ∙ (1 − 1 )
1 2 𝑛
2
1 1
𝑝1
𝑝2
1
𝑝𝑛
1
= 𝑚 (1 − 𝑝
) (1 − 𝑝
) ∙ … ∙ (1 − )
𝑝
𝑛
EYLER TEOREMASI. Agar a butun son 𝑚 bilan o`zaro tub bo`lsa, u holda
𝑎 𝜑(𝑚) = 1(𝑚𝑜𝑑𝑚) (1)
bo`ladi.
ISBOTI. 𝑎 1, 𝑎 2, … , 𝑎 𝜑(𝑚) (2) - m modul bo`yicha chegirmalarning keltirilgan sistemasi bo`lsin, u holda 2-teoremaga ko`ra,
𝑎𝑎 1, 𝑎𝑎 2, … , 𝑎𝑎 𝜑(𝑚) (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
𝑎 𝜑(𝑚)𝑎 1 ∙ 𝑎 2 ∙ … ∙ 𝑎 𝜑(𝑚) ≡ 𝑎 1 ∙ 𝑎 2 ∙ … ∙ 𝑎 𝜑(𝑚)(𝑚𝑜𝑑𝑚)
𝑎 1𝑎 2 ∙ … ∙ 𝑎 𝜑(𝑚) ko`paytma 𝑚 bilan o`zaro tub, shuning uchun taqqoslamaning xossasiga ko`ra, 𝑎 1𝑎 2 … 𝑎 𝜑(𝑚) 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 = 22 ekanligidan 𝜑(4) = 4 ∙ (1 − 1 = 2
2
kelib chiqadi. Demak, 𝑥 ≡ 10 ∙ 72−1(𝑚𝑜𝑑 4). Agar 10 ≡ 2 (𝑚𝑜𝑑 4), 7 ≡
3 (𝑚𝑜𝑑 4), 6 ≡ 2 (𝑚𝑜𝑑 4) taqqoslamalaran foydalansak 𝑥 ≡ 10 ∙
72−1(𝑚𝑜𝑑 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 𝑥 = 𝑥0 bo`lganda 𝑎𝑥0 ≡ 𝑏(𝑚𝑜𝑑𝑚)
taqqoslama to`g`ri bo`lsa, u holda 𝑥0 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) 𝑥0 = 3 + 6𝑡, ∀𝑡 ∈ ℤ 𝑥0 = 9, 15, … sonlar ham bu taqqoslamani qanoatlantiradi.
|
| |