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

Уикипедия — ашық энциклопедиясынан алынған мәлімет
Мұнда ауысу: шарлау, іздеу
Алғашқы мың мәні\varphi(n)

Эйлера функциясы \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),

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

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

\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)}.
мұндағы |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