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.