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.