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

Алғашқы мың мәні

АнықтамаӨңдеу

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

 

Онда

 

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

 

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

 

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

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

  +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.  , егер   — жай сан болса. Жекеше түрі:   болғанда  ;
  2.  , егер m мен   өзара жай болса. Яғни Эйлер функциясы мультипликативті;
  3.  , егер m мен   өзара жай болса. Бұл Эйлер теоремасы болып табылады;
  4.  
  5.  , если  Ең Кіші Ортақ Еселік, aл  Ең Үлкен Ортақ Бөлгіш.

Асимптоталық байланыстарӨңдеу

  1.   мұндағы   — белгілі бір тұрақты;
  2.  
  3.  
  4.  

Аналитикалық байланыстарӨңдеу

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

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

Си тіліндеӨңдеу

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