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

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

## Асимптоталық байланыстар
# \frac{Cn}{\ln\ln n}\leqslant\varphi(n)\leqslant n, мұндағы C — белгілі бір тұрақты;
# \sum_{n\leqslant x}\varphi(n)=\frac{3}{\pi^2}x^2+O(x\ln x);
# \sum_{k=1}^n\frac{k}{\varphi(k)}=O(n);
# \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|.
* \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 санын өшіріледі, ал нәтиже-көбейтінді сәйкесінше сол санға көбейтіліп өседі.

```c
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;
}
```


### [[Visual Basic|VB.Net]]

```vbnet
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 Sharp|F#]]

```ocaml
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
```


Санат:Арифметикалық функциялар
Санат:Сандар теориясы