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

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

 Анықтама 
 жай сандарға келесідей жіктелген  натурал саны берілсін: 


Онда

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

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

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

 Функцияның кейбір мәндері 
  +0  +1  +2  +3  +4  +5  +6  +7  +8  +9 0+  1  1  2  2  4  2  6  4  610+ 4  10  4  12  6  8  8  16  6  1820+ 8  12  10  22  8  20  12  18  12  2830+ 8  30  16  20  16  24  12  36  18  2440+ 16  40  12  42  20  24  22  46  16  4250+ 20  32  24  52  18  40  24  36  28  5860+ 16  60  30  36  32  48  20  66  32  4470+ 24  70  24  72  36  40  36  60  24  7880+ 32  54  40  82  24  64  42  56  40  8890+ 24  72  44  60  46  72  32  96  42  60

 Қасиеттері
 , егер  — жай сан болса. Жекеше түрі:  болғанда ;
 , егер m мен  өзара жай болса. Яғни Эйлер функциясы мультипликативті;
 , егер m мен  өзара жай болса. Бұл Эйлер теоремасы болып табылады;

 , если  — Ең кіші ортақ еселік, aл  — Ең үлкен ортақ бөлгіш.

 Асимптоталық байланыстар
  мұндағы  — белгілі бір тұрақты;




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





 Дирихле қатарын  коэффициенттерімен Риман дзета-функциясы арқылы өрнектеуге болады:

 Ламберт қатары қосындысын  коэффициенттерімен:

 мұндағы .
 , мұндағы .

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

 Си тілінде
Төмендегі функция  көбейтіндісін есептейді. Бұл  санын жай сандарға көбейткіштерге 2-ден бастап барлық сандарға бөлу арқылы іске асырылады; егер  санға бөлінсе, бұл сан  санын өшіріледі, ал нәтиже-көбейтінді сәйкесінше сол санға көбейтіліп өседі.
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

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