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

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

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

Анықтама

$p_{i}:\,$ жай сандарға келесідей жіктелген $n\,$ натурал саны берілсін:

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

Онда

$\varphi (n)=\prod _{i=1}^{k}p_{i}^{\alpha _{i}-1}\left(p_{i}-1\right)$

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

$\varphi (1)=1.$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• $\sum _{1\leqslant k\leqslant n \atop (k,\;n)=1}k={\frac {1}{2}}n\varphi (n)$, мұндағы $n>1$.

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

Си тілінде

Төмендегі функция $\varphi (n)=\prod _{i=1}^{k}p_{i}^{\alpha _{i}-1}\left(p_{i}-1\right)$ көбейтіндісін есептейді. Бұл $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