Эйлер функциясы

Алғашқы мың мәні$\phi (n)$

Эйлера функциясы $\phi (n)$, мұндағы $n$ — натурал сан, $n$ санынан үлкен емес әрі онымен өзара жай натурал сандар санына тең. Эйлера бұл функцияны сандар теориясы еңбектерінде алғашқы болып пайдаланғандықтан соның құрметіне осылай талып кетті.

Анықтама

$p_i:$ жай сандарға келесідей жіктелген $n$ натурал саны берілсін:

$n=\prod _{i=1}^k{p}_i^{{\alpha }_i}$

Онда

$\phi (n)=\prod _{i=1}^k{p}_i^{{\alpha }_i-1}(p_i-1)$

функциясы Эйлер функциясы деп аталады. Мұндағы

$\phi (1)=1.$

болады деп саналады. Эйлера функциясын Эйлер көбейтіндісі ретінде де өрнектеуге болады:

$\phi (n)=n\prod _{p\mid n}(1-\frac{1}{p}),$

мұндағы $p$ — $n$ санының жай сандарға жіктелуінде қатысатын барлық жай сандарды қабылдайды.

Функцияның кейбір мәндері

$\phi (n)$	+0	+1	+2	+3	+4	+5	+6	+7	+8	+9
0+		1	1	2	2	4	2	6	4	6
10+	4	10	4	12	6	8	8	16	6	18
20+	8	12	10	22	8	20	12	18	12	28
30+	8	30	16	20	16	24	12	36	18	24
40+	16	40	12	42	20	24	22	46	16	42
50+	20	32	24	52	18	40	24	36	28	58
60+	16	60	30	36	32	48	20	66	32	44
70+	24	70	24	72	36	40	36	60	24	78
80+	32	54	40	82	24	64	42	56	40	88
90+	24	72	44	60	46	72	32	96	42	60

Қасиеттері

1. $\phi (p^n)=p^{n-1}(p-1)$, егер $p$ — жай сан болса. Жекеше түрі: $n=1$ болғанда $\phi (p)=p-1$;
2. $\phi (mn)=\phi (m)\phi (n)$, егер m мен $n$ өзара жай болса. Яғни Эйлер функциясы мультипликативті;
3. $a^{\phi (m)}\equiv 1(\mathrm{mod}m)$, егер m мен $a$ өзара жай болса. Бұл Эйлер теоремасы болып табылады;
4. $\phi (m^k)=m^{k-1}\phi (m);$
5. $mn=(m,n)[m,n],\phi (m)\phi (n)=\phi ((m,n))\phi ([m,n]),\phi (mn)\phi ((m,n))=\phi (m)\phi (n)(m,n)$, если $[m,n]$ — Ең кіші ортақ еселік, aл $(m,n)$ — Ең үлкен ортақ бөлгіш.

Асимптоталық байланыстар

1. $\frac{Cn}{\ln \ln n}⩽\phi (n)⩽n,$ мұндағы $C$ — белгілі бір тұрақты;
2. $\sum _{n⩽x}\phi (n)=\frac{3}{{\pi }^2}{x}^2+O(x\ln x);$
3. $\sum _{k=1}^n\frac{k}{\phi (k)}=O(n);$
4. $\sum _{k=1}^n\frac{1}{\phi (k)}=O(\ln n).$

Аналитикалық байланыстар

• Эйлер функциясы Мёбиус функциясымен де байланысы бар:

• $\phi (n)=\sum _{d\mid n}d\cdot \mu \left(\frac{n}{d}\right);$
• $\sum _{k=1}^n\phi (k)=\frac{1}{2}(1+\sum _{k=1}^n\mu (k){\lfloor \frac{n}{k}\rfloor }^2);$
• $\sum _{k=1}^n\frac{\phi (k)}{k}=\sum _{k=1}^n\frac{\mu (k)}{k}\lfloor \frac{n}{k}\rfloor ;$
• $\sum _{d\mid n}\frac{{\mu }^2(d)}{\phi (d)}=\frac{n}{\phi (n)}.$

• $\sum _{d\mid n,d\in N}\phi (d)=n.$
• Дирихле қатарын $\phi (n)$ коэффициенттерімен Риман дзета-функциясы арқылы өрнектеуге болады:

  $\sum _{n=1}^{\mathrm{\infty }}\frac{\phi (n)}{n^s}=\frac{\zeta (s-1)}{\zeta (s)}.$

• Ламберт қатары қосындысын $\phi (n)$ коэффициенттерімен:

  $\sum _{n=1}^{\mathrm{\infty }}\frac{\phi (n)q^n}{1-q^n}=\frac{q}{(1-q{)}^2},$

мұндағы $|q|<1$.

• $\sum _{\genfrac{}{}{0ex}{}{1⩽k⩽n}{(k,n)=1}}k=\frac{1}{2}n\phi (n)$, мұндағы $n>1$.

Компьютерлік іске асырылуы

Си тілінде

Төмендегі функция $\phi (n)=\prod _{i=1}^k{p}_i^{{\alpha }_i-1}(p_i-1)$ көбейтіндісін есептейді. Бұл $n$ санын жай сандарға көбейткіштерге 2-ден бастап барлық сандарға бөлу арқылы іске асырылады; егер $n$ санға бөлінсе, бұл сан $n$ санын өшіріледі, ал нәтиже-көбейтінді сәйкесінше сол санға көбейтіліп өседі.

int phi(int n)
{
  int ret = 1, p;
  for(p = 2; p * p <= n; p++)
  {
    if (n % p == 0)
    {
      n /= p;
      while(n % p == 0) 
      {
        n /= p;
        ret *= p;
      }
      ret *= p - 1;
    }
  }
  return n > 1 ? ret * (n - 1) : ret;
}

VB.Net

    Private Function phi(ByVal n As Integer) As Integer
        Dim ret As Integer = 1, p As Integer = 2
        For p = 2 To n / p
            If n Mod p = 0 Then
                n /= p
                While n Mod p = 0
                    n /= p
                    ret *= p
                End While
                ret *= p - 1
            End If
        Next
        Return If(n > 1, ret * (n - 1), ret)
    End Function

F#

let phi n =
    let rec nod a b = if b = 0 then a
                      else nod b (a % b)
    { 1 .. n-1 }
    |> Seq.filter (fun i -> nod i n = 1)
    |> Seq.length

Үлгі:Math-stub