Eyler funksiyasi

23:20 / 18.02.2023
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.