Eyler funksiyasi
Ta’rif
Eyler funksiyasi 𝜙(𝑛) (ba’zida 𝜑(𝑛) yoki 𝑝ℎ𝑖(𝑛) orqali ifodalanadi) – bu 1 dan n gacha bo’lgan sonlar oralig’ida n bilan o’zaro tub sonlar sonidir. Boshqacha qilib aytadigan bo’lsak, bu [1;n] oralig’idagi n bilan EKUBi birga teng bo’ladigan sonlar sonidir.
Funksiyaning dastlabki bir nechta qiymati:
\(\phi(1) = 1 \\ \phi(2) = 1 \\ \phi(3) = 2 \\ \phi(4) = 2 \\ \phi(5) = 4 \\ \phi(6) = 2 \\ \phi(7) = 6\)
Xususiyatlari
Eyler funksiyasining quyidagi uchta xususiyati ixtiyoriy son uchun uning qiymatini hisoblashni o’rganishga yetarli:
- Agar 𝑝 tub son bo’lsa, 𝜙(𝑝) = 𝑝 − 1.
- Agar 𝑝 tub va 𝑎 natural son bo’lsa, \(\phi(𝑝^𝑎) = 𝑝^𝑎 − 𝑝^{𝑎−1}\). (𝑝𝑎 bilan o’zaro tub bo’lmaganlar faqatgina 𝑝𝑘(𝑘 ∈ 𝑁) ko’rinishidagi sonlardir, ya’ni ja’mi \(\frac{𝑝^𝑎}{p} = 𝑝^{𝑎−1}\) dona).
- Agar 𝑎 va 𝑏 o’zaro tub bo’lsa, 𝜙(𝑎𝑏) = 𝜙(𝑎) 𝜙(𝑏) (Eyler funksiyasining “multiplikativlik” xususiyati)
(Bu fakt xitoycha qoldiqlar teoremasi asosida olingan. 𝑧 ≤ 𝑎𝑏 tasodifiy sonni
ko’raylik. 𝑧 ni 𝑎 ga va 𝑏 ga bo’lgandagi qoldiqni mos ravishda 𝑥 va 𝑦 deb
belgilab olamiz. Shunda 𝑧 soni 𝑎𝑏 bilan o’zaro tub bo’ladi qachonki 𝑧 soni 𝑎
bilan ham, 𝑏 bilan ham alohida ravishda o’zaro tub bo’lsa, yoki, xuddi shuning
o’zi, 𝑥 soni 𝑎 bilan o’zaro tub va 𝑦 soni 𝑏 bilan o’zaro tub bo’lsa. Xitoyning
qoldiqlar teoremasi inobatga olinib, ixtiyoriy 𝑥 va 𝑦 juftlik (𝑥 ≤ 𝑎, 𝑦 ≤ 𝑏)
qaysidir bir 𝑧 ni ifodalaydi, ya’ni har bir 𝑧 uchun hosil bo’ladigan 𝑥 va 𝑦 juftlik
takrorlanmas bo’ladi.)
Bu yerdan ixtiyoriy 𝑛 soni uchun uning kanonik ko’rinishi (tub ko’paytuvchilari yoyilmasi) orqali Eyler funksiyasini aniqlashimiz mumkin, agar:
\(n=p_1^{a_1} * p_2^{a_2} * \dots * p_k^{a_k}\)
(barcha \(p_i\)lar tub) bo’lsa
\(\phi(n)=\phi(p_1^{a_1}) * \phi(p_2^{a_2}) * \dots * \phi(p_k^{a_k}) = (p_1^{a_1}-p_1^{a_1-1}) * (p_2^{a_2}-p_2^{a_2-1}) * \dots * (p_k^{a_k}-p_k^{a_k-1}) = n * (1 - \dfrac{1}{p_1}) * (1 - \dfrac{1}{p_2})*\dots*(1 - \dfrac{1}{p_k})\)
Dasturiy ifodalanishi
Eyler funksiyasini hisoblaydigan eng sodda kod, kanonik ko’rinishga keltirish orqali \(O (\sqrt{n})\) da hisoblanadi.
int phi(int n) {
int result = n;
for (int i = 2; i * i <= n; ++i)
if (n % i == 0) {
while (n % i == 0)
n /= i;
result -= result / i;
}
if (n > 1)
result -= result / n;
return result;
}
Eyler funksiyasini hisoblash uchun biz 𝑛 sonini kanonik ko’rinishidagi tub sonlarni aniqlashimiz kerak. Kanonik ko’rinishni kanonik ko’rinishga keltirishning samarali usullari orqali \(O (\sqrt{n})\) dan ham tezkor aniqlash mumkin.
Eyler funksiyasidan ilovalar
Eyler funktsiyasining eng mashhur va muhim xususiyati Eyler teoremasida quyidagicha ifodalanadi:
\(a^{\phi(m)} \equiv ({\rm mod}\ m),\) Bu yerda 𝑎 va 𝑚 o’zaro tub. m tub bo’lgan holatda Eyler teoremasi Fermaning kichik teoremasiga aylanadi. \(a^{m-1} \equiv ({\rm mod}\ m),\) eyler teoremasi amaliy qo’llanmalarda juda keng tarqalgan. Masalan: Modul bo’yicha teskari element.






