FUNCȚIA TOTIENT A LUI EULER - TECHCODEVIEW.COM

Funcția Totient a lui Euler Φ(n) pentru o intrare n este numărul de numere din {1, 2, 3, …, n-1} care sunt relativ prime cu n, adică numerele al căror GCD (cel mai mare divizor comun) cu n este 1.

Exemple:

Φ(1) = 1
mcd(1, 1) este 1

Φ(2) = 1
mcd(1, 2) este 1, dar mcd(2, 2) este 2.

Φ(3) = 2
mcd(1, 3) este 1 și mcd(2, 3) este 1

Φ(4) = 2
mcd(1, 4) este 1 și mcd(3, 4) este 1

Φ(5) = 4
mcd(1, 5) este 1, mcd(2, 5) este 1,
mcd(3, 5) este 1 și mcd(4, 5) este 1

Φ(6) = 2
mcd(1, 6) este 1 și mcd(5, 6) este 1,

Practică recomandată Funcția Euler Totient Încercați!

Cum se calculează Φ(n) pentru o intrare n?
A solutie simpla este să iterați prin toate numerele de la 1 la n-1 și să numărați numerele cu mcd cu n ca 1. Mai jos este implementarea metodei simple de a calcula funcția Totient a lui Euler pentru un întreg de intrare n.

 // A simple C program to calculate Euler's Totient Function #include  // Function to return gcd of a and b int gcd(int a, int b) {  if (a == 0)  return b;  return gcd(b % a, a); } // A simple method to evaluate Euler Totient Function int phi(unsigned int n) {  unsigned int result = 1;  for (int i = 2; i < n; i++)  if (gcd(i, n) == 1)  result++;  return result; } // Driver program to test above function int main() {  int n;  for (n = 1; n <= 10; n++)  printf('phi(%d) = %d
', n, phi(n));  return 0; }>

Java

 // A simple java program to calculate // Euler's Totient Function import java.io.*; class GFG {  // Function to return GCD of a and b  static int gcd(int a, int b)  {  if (a == 0)  return b;  return gcd(b % a, a);  }  // A simple method to evaluate  // Euler Totient Function  static int phi(int n)  {  int result = 1;  for (int i = 2; i < n; i++)  if (gcd(i, n) == 1)  result++;  return result;  }  // Driver code  public static void main(String[] args)  {  int n;  for (n = 1; n <= 10; n++)  System.out.println('phi(' + n + ') = ' + phi(n));  } } // This code is contributed by sunnusingh>

Python3

 # A simple Python3 program  # to calculate Euler's  # Totient Function # Function to return # gcd of a and b def gcd(a, b): if (a == 0): return b return gcd(b % a, a) # A simple method to evaluate # Euler Totient Function def phi(n): result = 1 for i in range(2, n): if (gcd(i, n) == 1): result+=1 return result # Driver Code for n in range(1, 11): print('phi(',n,') = ', phi(n), sep = '') # This code is contributed # by Smitha>

 // A simple C# program to calculate // Euler's Totient Function using System; class GFG {  // Function to return GCD of a and b  static int gcd(int a, int b)  {  if (a == 0)  return b;  return gcd(b % a, a);  }  // A simple method to evaluate  // Euler Totient Function  static int phi(int n)  {  int result = 1;  for (int i = 2; i < n; i++)  if (gcd(i, n) == 1)  result++;  return result;  }  // Driver code  public static void Main()  {  for (int n = 1; n <= 10; n++)  Console.WriteLine('phi(' + n + ') = ' + phi(n));  } } // This code is contributed by nitin mittal>

Javascript

 >>>PHP <Φphp // PHP program to calculate  // Euler's Totient Function // Function to return  // gcd of a and b function gcd($a, $b) {  if ($a == 0)  return $b;  return gcd($b % $a, $a); } // A simple method to evaluate // Euler Totient Function function phi($n) {  $result = 1;  for ($i = 2; $i <$n; $i++)  if (gcd($i, $n) == 1)  $result++;  return $result; } // Driver Code for ($n = 1; $n <= 10; $n++)  echo 'phi(' .$n. ') =' . phi($n).'
'; // This code is contributed by Sam007 Φ>>>>C++ // A simple C++ program to calculate // Euler's Totient Function  #include  using namespace std;  // Function to return gcd of a and b  int gcd(int a, int b)  {   if (a == 0)   return b;   return gcd(b % a, a);  }  // A simple method to evaluate Euler Totient Function  int phi(unsigned int n)  {   unsigned int result = 1;   for (int i = 2; i < n; i++)   if (gcd(i, n) == 1)   result++;   return result;  }  // Driver program to test above function  int main()  {   int n;   for (n = 1; n <= 10; n++)   cout << 'phi('<  
  Ieșire  phi(1) = 1 phi(2) = 1 phi(3) = 2 phi(4) = 2 phi(5) = 4 phi(6) = 2 phi(7) = 6 phi(8) = 4 phi( 9) = 6 phi(10) = 4
 
 

   
Codul de mai sus apelează funcția gcd O(n) ori. Complexitatea temporală a funcției mcd este O(h) unde h este numărul de cifre dintr-un număr mai mic de două numere date. Prin urmare, o limită superioară pe      complexitatea timpului      din soluția de mai sus este O(N^2 log N) [Cum Φ poate fi cel mult Log₁₀n cifre în toate numerele de la 1 la n]
       Spațiu auxiliar:      O(log N)
   
Mai jos este a    Soluție mai bună    . Ideea se bazează pe formula produsului a lui Euler, care afirmă că valoarea funcțiilor totale este sub factorul primi global al produsului p a lui n.
 
 

 
 Formula spune practic că valoarea lui Φ(n) este egală cu n produs secundar înmulțit al lui (1 – 1/p) pentru toți factorii primi p ai lui n. De exemplu, valoarea lui Φ(6) = 6 * (1-1/2) * (1 – 1/3) = 2.  
Putem găsi toți factorii primi folosind ideea folosită în acest post.
 1) Inițializați : rezultat = n  
2) Rulați o buclă de la „p” = 2 la sqrt(n), faceți următoarele pentru fiecare „p”.  
a) Dacă p împarte n, atunci  
Set: rezultat = rezultat * (1,0 - (1,0 / (float) p));  
Împărțiți toate aparițiile lui p în n.  
3) Returnați rezultatul
  
Mai jos este implementarea formulei de produs a lui Euler.
C++ // C++ program to calculate Euler's  // Totient Function using Euler's // product formula #include  using namespace std; int phi(int n) {    // Initialize result as n  float result = n;     // Consider all prime factors of n   // and for every prime factor p,  // multiply result with (1 - 1/p)  for(int p = 2; p * p <= n; ++p)  {    // Check if p is a prime factor.  if (n % p == 0)  {    // If yes, then update n and result  while (n % p == 0)  n /= p;    result *= (1.0 - (1.0 / (float)p));  }  }    // If n has a prime factor greater than sqrt(n)  // (There can be at-most one such prime factor)  if (n>1) rezultat -= rezultat / n;  //Deoarece în mulțimea {1,2,....,n-1}, toate numerele sunt relativ prime cu n //dacă n este un număr prim returnează (int)rezultat; } // Cod driver int main() { int n;    pentru (n = 1; n<= 10; n++)  {  cout << 'Phi' << '('   << n << ')' << ' = '  << phi(n) <C // C program to calculate Euler's Totient Function // using Euler's product formula #include  int phi(int n) {  float result = n; // Initialize result as n  // Consider all prime factors of n and for every prime  // factor p, multiply result with (1 - 1/p)  for (int p = 2; p * p <= n; ++p) {    // Check if p is a prime factor.  if (n % p == 0) {    // If yes, then update n and result  while (n % p == 0)  n /= p;  result *= (1.0 - (1.0 / (float)p));  }  }  // If n has a prime factor greater than sqrt(n)  // (There can be at-most one such prime factor)  if (n>1) rezultat -= rezultat / n;  //Deoarece în mulțimea {1,2,....,n-1}, toate numerele sunt relativ prime cu n //dacă n este un număr prim returnează (int)rezultat; } // Program driver pentru a testa funcția de mai sus int main() { int n;  pentru (n = 1; n<= 10; n++)  printf('phi(%d) = %d
', n, phi(n));  return 0; }>Java // Java program to calculate Euler's Totient // Function using Euler's product formula import java.io.*; class GFG {  static int phi(int n)  {  // Initialize result as n  float result = n;  // Consider all prime factors of n and for  // every prime factor p, multiply result  // with (1 - 1/p)  for (int p = 2; p * p <= n; ++p) {  // Check if p is a prime factor.  if (n % p == 0) {  // If yes, then update n and result  while (n % p == 0)  n /= p;  result *= (1.0 - (1.0 / (float)p));  }  }  // If n has a prime factor greater than sqrt(n)  // (There can be at-most one such prime factor)  if (n>1) rezultat -= rezultat / n;  //Deoarece în mulțimea {1,2,....,n-1}, toate numerele sunt relativ prime cu n //dacă n este un număr prim returnează (int)rezultat;  } // Program driver pentru a testa funcția de mai sus public static void main(String args[]) { int n;  pentru (n = 1; n<= 10; n++)  System.out.println('phi(' + n + ') = ' + phi(n));  } } // This code is contributed by Nikita Tiwari.>Python3 # Python 3 program to calculate # Euler's Totient Function # using Euler's product formula def phi(n) : result = n # Initialize result as n # Consider all prime factors # of n and for every prime # factor p, multiply result with (1 - 1 / p) p = 2 while p * p<= n : # Check if p is a prime factor. if n % p == 0 : # If yes, then update n and result while n % p == 0 : n = n // p result = result * (1.0 - (1.0 / float(p))) p = p + 1 # If n has a prime factor # greater than sqrt(n) # (There can be at-most one # such prime factor) if n>1 : rezultat -= rezultat // n #Deoarece în mulțimea {1,2,.....,n-1}, toate numerele sunt relativ prime cu n #dacă n este un număr prim return int(rezultat) # Driver program pentru a testa funcția de mai sus pentru n în intervalul (1, 11) : print('phi(', n, ') = ', phi(n)) # Acest cod este contribuit # de Nikita Tiwari.>>>C# // C# program to calculate Euler's Totient // Function using Euler's product formula using System; class GFG {    static int phi(int n)  {    // Initialize result as n  float result = n;  // Consider all prime factors  // of n and for every prime   // factor p, multiply result  // with (1 - 1 / p)  for (int p = 2; p * p <= n; ++p)   {    // Check if p is a prime factor.  if (n % p == 0)   {    // If yes, then update  // n and result  while (n % p == 0)  n /= p;  result *= (float)(1.0 - (1.0 / (float)p));  }  }  // If n has a prime factor   // greater than sqrt(n)  // (There can be at-most   // one such prime factor)  if (n>1) rezultat -= rezultat / n;  //Deoarece în mulțimea {1,2,....,n-1}, toate numerele sunt relativ prime cu n //dacă n este un număr prim returnează (int)rezultat;  } // Cod driver public static void Main() { int n;  pentru (n = 1; n<= 10; n++)  Console.WriteLine('phi(' + n + ') = ' + phi(n));  } } // This code is contributed by nitin mittal.>Javascript // Javascript program to calculate  // Euler's Totient Function  // using Euler's product formula function phi(n) {  // Initialize result as n  let result = n;   // Consider all prime factors  // of n and for every prime  // factor p, multiply result   // with (1 - 1/p)  for (let p = 2; p * p <= n; ++p)   {    // Check if p is  // a prime factor.  if (n % p == 0)   {    // If yes, then update  // n and result  while (n % p == 0)  n /= p;  result *= (1.0 - (1.0 / p));  }  }  // If n has a prime factor greater   // than sqrt(n) (There can be at-most  // one such prime factor)  if (n>1) rezultat -= rezultat / n;  //Deoarece în mulțimea {1,2,....,n-1}, toate numerele sunt relativ prime cu n //dacă n este un număr prim returnează parseInt(rezultat); } // Cod șofer pentru (fie n = 1; n<= 10; n++)  document.write(`phi(${n}) = ${phi(n)} `);   // This code is contributed by _saurabh_jaiswal>PHP <Φphp // PHP program to calculate  // Euler's Totient Function  // using Euler's product formula function phi($n) {  // Initialize result as n  $result = $n;   // Consider all prime factors  // of n and for every prime  // factor p, multiply result   // with (1 - 1/p)  for ($p = 2; $p * $p <= $n; ++$p)   {    // Check if p is  // a prime factor.  if ($n % $p == 0)   {    // If yes, then update  // n and result  while ($n % $p == 0)  $n /= $p;  $result *= (1.0 - (1.0 / $p));  }  }  // If n has a prime factor greater   // than sqrt(n) (There can be at-most  // one such prime factor)  if ($n>1) $rezultat -= $rezultat / $n;  //Deoarece în mulțimea {1,2,....,n-1}, toate numerele sunt relativ prime cu n //dacă n este un număr prim returnează intval($rezultat); } // Cod driver pentru ($n = 1; $n<= 10; $n++) echo 'phi(' .$n. ') =' . phi($n).'
';   // This code is contributed by Sam007 Φ>>>>  
  Ieșire  Phi(1) = 1 Phi(2) = 1 Phi(3) = 2 Phi(4) = 2 Phi(5) = 4 Phi(6) = 2 Phi(7) = 6 Phi(8) = 4 Phi( 9) = 6 Phi(10) = 4
     Complexitatea timpului:    O(Φ n log n)  
    Spațiu auxiliar:    O(1)
 Putem evita calculele în virgulă mobilă în metoda de mai sus. Ideea este să numărăm toți factorii primi și multiplii lor și să scădem acest număr din n pentru a obține valoarea funcției totient (factorii primi și multiplii factorilor primi nu vor avea mcd ca 1)
 1) Inițializați rezultatul ca n  
2) Luați în considerare fiecare număr „p” (unde „p” variază de la 2 la Φ(n)).  
Dacă p împarte n, atunci procedați după cum urmează  
a) Scădeți toți multiplii lui p de la 1 la n [toți multiplii lui p  
va avea Gcd mai mult de 1 (cel puțin p) cu n]  
b) Actualizați n împărțindu-l în mod repetat la p.  
3) Dacă n redus este mai mare de 1, atunci eliminați toți multiplii  
de n din rezultat.
Mai jos este implementarea algoritmului de mai sus.
C++ // C++ program to calculate Euler's // Totient Function #include  using namespace std; int phi(int n) {  // Initialize result as n  int result = n;     // Consider all prime factors of n   // and subtract their multiples   // from result  for(int p = 2; p * p <= n; ++p)  {    // Check if p is a prime factor.  if (n % p == 0)   {    // If yes, then update n and result  while (n % p == 0)  n /= p;    result -= result / p;  }  }    // If n has a prime factor greater than sqrt(n)  // (There can be at-most one such prime factor)  if (n>1) rezultat -= rezultat / n;    returnează rezultatul; } // Cod driver int main() { int n;  pentru (n = 1; n<= 10; n++)  {  cout << 'Phi' << '('   << n << ')' << ' = '  << phi(n) << endl;  }  return 0; } // This code is contributed by koulick_sadhu>C // C program to calculate Euler's Totient Function #include  int phi(int n) {  int result = n; // Initialize result as n  // Consider all prime factors of n and subtract their  // multiples from result  for (int p = 2; p * p <= n; ++p) {    // Check if p is a prime factor.  if (n % p == 0) {    // If yes, then update n and result  while (n % p == 0)  n /= p;  result -= result / p;  }  }  // If n has a prime factor greater than sqrt(n)  // (There can be at-most one such prime factor)  if (n>1) rezultat -= rezultat / n;  returnează rezultatul; } // Program driver pentru a testa funcția de mai sus int main() { int n;  pentru (n = 1; n<= 10; n++)  printf('phi(%d) = %d
', n, phi(n));  return 0; }>Java // Java program to calculate  // Euler's Totient Function import java.io.*; class GFG  { static int phi(int n) {  // Initialize result as n  int result = n;   // Consider all prime factors   // of n and subtract their  // multiples from result  for (int p = 2; p * p <= n; ++p)  {    // Check if p is   // a prime factor.  if (n % p == 0)   {    // If yes, then update  // n and result  while (n % p == 0)  n /= p;  result -= result / p;  }  }  // If n has a prime factor  // greater than sqrt(n)  // (There can be at-most   // one such prime factor)  if (n>1) rezultat -= rezultat / n;  returnează rezultatul; } // Cod driver public static void main (String[] args) { int n;  pentru (n = 1; n<= 10; n++)  System.out.println('phi(' + n +   ') = ' + phi(n)); } } // This code is contributed by ajit>Python3 # Python3 program to calculate  # Euler's Totient Function def phi(n): # Initialize result as n result = n; # Consider all prime factors # of n and subtract their # multiples from result p = 2; while(p * p <= n): # Check if p is a  # prime factor. if (n % p == 0): # If yes, then  # update n and result while (n % p == 0): n = int(n / p); result -= int(result / p); p += 1; # If n has a prime factor # greater than sqrt(n) # (There can be at-most  # one such prime factor) if (n>1): rezultat -= int(rezultat / n); returnează rezultatul; # Cod driver pentru n în interval (1, 11): print('phi(',n,') =', phi(n)); # Acest cod este contribuit # de mits>>>C# // C# program to calculate  // Euler's Totient Function using System; class GFG {   static int phi(int n) { // Initialize result as n int result = n;  // Consider all prime  // factors of n and  // subtract their  // multiples from result for (int p = 2;  p * p <= n; ++p) {    // Check if p is   // a prime factor.  if (n % p == 0)   {    // If yes, then update  // n and result  while (n % p == 0)  n /= p;  result -= result / p;  } } // If n has a prime factor // greater than sqrt(n) // (There can be at-most  // one such prime factor) if (n>1) rezultat -= rezultat / n; returnează rezultatul; } // Cod driver static public void Main () { int n;  pentru (n = 1; n<= 10; n++)  Console.WriteLine('phi(' + n +   ') = ' +  phi(n)); } } // This code is contributed  // by akt_mit>Javascript // Javascript program to calculate  // Euler's Totient Function function phi(n) {  // Initialize   // result as n  let result = n;   // Consider all prime   // factors of n and subtract   // their multiples from result  for (let p = 2;   p * p <= n; ++p)  {    // Check if p is   // a prime factor.  if (n % p == 0)   {    // If yes, then   // update n and result  while (n % p == 0)  n = parseInt(n / p);  result -= parseInt(result / p);  }  }  // If n has a prime factor  // greater than sqrt(n)  // (There can be at-most   // one such prime factor)  if (n>1) rezultat -= parseInt(rezultat / n);  returnează rezultatul; } // Cod șofer pentru (fie n = 1; n<= 10; n++)  document.write(`phi(${n}) = ${phi(n)} `);   // This code is contributed  // by _saurabh_jaiswal>PHP <Φphp // PHP program to calculate  // Euler's Totient Function function phi($n) {  // Initialize   // result as n  $result = $n;   // Consider all prime   // factors of n and subtract   // their multiples from result  for ($p = 2;   $p * $p <= $n; ++$p)  {    // Check if p is   // a prime factor.  if ($n % $p == 0)   {    // If yes, then   // update n and result  while ($n % $p == 0)  $n = (int)$n / $p;  $result -= (int)$result / $p;  }  }  // If n has a prime factor  // greater than sqrt(n)  // (There can be at-most   // one such prime factor)  if ($n>1) $rezultat -= (int)$rezultat / $n;  returnează $rezultat; } // Cod driver pentru ($n = 1; $n<= 10; $n++)  echo 'phi(', $n,') =',   phi($n), '
';   // This code is contributed  // by ajit Φ>>>>  
  Ieșire  Phi(1) = 1 Phi(2) = 1 Phi(3) = 2 Phi(4) = 2 Phi(5) = 4 Phi(6) = 2 Phi(7) = 6 Phi(8) = 4 Phi( 9) = 6 Phi(10) = 4
     Complexitatea timpului:    O(Φ n log n)  
    Spațiu auxiliar:    O(1)
 Să luăm un exemplu pentru a înțelege algoritmul de mai sus.
 n = 10.  
Inițializare: rezultat = 10  
  
2 este un factor prim, deci n = n/i = 5, rezultat = 5  
3 nu este un factor prim.  
  
Bucla for se oprește după 3, deoarece 4*4 nu este mai mic sau egal  
la 10.  
  
După bucla for, rezultat = 5, n = 5  
Deoarece n> 1, rezultat = rezultat - rezultat/n = 4
    Câteva proprietăți interesante ale funcției Totient a lui Euler       
    1)    Pentru o    număr prim p    ,phi(p) = p – 1
k cel mai apropiat vecin
     Dovada:    
 unde k este orice număr aleatoriu șiNumăr total de la 1 la p = p Număr pentru care, adică numărul p însuși, deci scăzând 1 din pphi(p) = p - 1
    Exemple:     
 phi(5) = 5 - 1 = 4phi(13) = 13 - 1 = 12phi(29) = 29 - 1 = 28
  
    2)    Pentru    două numere prime a și b     phi(a cdot b) = phi(a) cdot phi(b) = (a – 1) cdot (b – 1) , folosit in  Algoritmul RSA  
     Dovada:    
 phi(acdot b) = phi(a) cdot phi(b), unde a și b sunt numere primephi(a) = a - 1,phi(b) = b - 1Numărul total de la 1 la ab = ab Multiplii totali ai a de la 1 la ab =frac{a cdot b} {a}=bMultiplii totali ai lui b de la 1 la ab =frac{a cdot b} {b}=a    Exemplu:    a = 5, b = 7, ab = 35 Multiplii ai a =frac {35} {5}= 7 {5, 10, 15, 20, 25, 30, 35} Multiplii ai lui b =frac {35} {7}= 5 {7, 14, 21, 28, 35}    Poate exista o dublă numărare?    (vizionați cu atenție exemplul de mai sus, încercați cu altele    numere prime    de asemenea, pentru mai multă înțelegere) Desigur, am număratab     de două ori    în multiplii a și multiplii lui b deci, Multiplii totali = a + b - 1 (cu caregcd 
eq 1cuab)phi(ab) = ab - (a + b - 1), eliminând toate numărul cugcd 
eq 1cuab phi(ab) = a(b - 1) - (b - 1)phi(ab) = (a - 1) cdot (b - 1)phi(ab) = phi(a) cdot phi(b)
    Exemple:    
 phi(5 cdot 7) = phi(5) cdot phi(7) = (5 - 1) cdot (7 - 1) = 24phi(3 cdot 5) = phi(3) cdot phi(5) = (3 - 1) cdot (5 - 1) = 8phi(3 cdot 7) = phi(3) cdot phi(7) = (3 - 1) cdot (7 - 1) = 12
  
    3)    Pentru    un număr prim p    ,phi(p ^ k) = p ^ k – p ^ {k – 1}
     Dovada:    
 phi(p^k) = p ^ k - p ^{k - 1}, unde p este un număr primNumerele totale de la 1 lap ^ k = p ^ kMultipli totali aip = frac {p ^ k} {p} = p ^ {k - 1}Eliminarea acestor multipli ca la eigcd 
eq 1    Exemplu:    p = 2, k = 5,p ^ k= 32 Multiplii de 2 (ca și în cazul lorgcd 
eq 1) = 32 / 2 = 16 {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32}phi(p ^ k) = p ^ k - p ^ {k - 1}
    Exemple:    
Freddie Mercury născut
 phi(2 ^ 5) = 2 ^ 5 - 2 ^ {5 - 1} = 32 - 16 = 16phi(5 ^ 3) = 5 ^ 3 - 5 ^ {3 - 1} = 125 - 25 = 100phi(3 ^ 5) = 3 ^ 5 - 3 ^ {5 - 1} = 243 - 81 = 162
  
    4)    Pentru    două numere a și b     phi(a cdot b)  = phi(a) cdot phi(b)  cdot frac {gcd(a, b)} {phi(gcd(a, b))}
     Caz special: mcd(a, b) = 1    
 phi(a cdot b) = phi(a) cdot phi(b) cdot frac {1} {phi(1)} = phi(a) cdot phi(b)
     Exemple:    
     Caz special :    gcd(a, b) = 1    ,    phi(a cdot b) = phi(a) cdot phi(b)         phi(2 cdot 9) = phi(2) cdot phi(9) = 1 cdot 6 = 6phi(8 cdot 9) = phi(8) cdot phi(9) = 4 cdot 6 = 24phi(5 cdot 6) = phi(5) cdot phi(6) = 4 cdot 2 = 8     Caz normal:    gcd(a, b) 
eq 1    ,    phi(a cdot b) = phi(a) cdot phi(b) cdot frac {gcd(a, b)} {phi(gcd(a, b))}phi(4 cdot 6) = phi(4) cdot phi(6) cdot frac {gcd(4, 6)} {phi(gcd(4, 6))} = 2 cdot 2 cdot frac{2}{1} = 2 cdot 2 cdot 2 = 8phi(4 cdot 8) = phi(4) cdot phi(8) cdot frac {gcd(4, 8)} {phi(gcd(4, 8))} = 2 cdot 4 cdot frac{4}{2} = 2 cdot 4 cdot 2 = 16phi(6 cdot 8) = phi(6) cdot phi(8) cdot frac {gcd(6, 8)} {phi(gcd(6, 8))} = 2 cdot 4 cdot frac{2}{1} = 2 cdot 4 cdot 2 = 16
    5)    Suma valorilor funcțiilor totale ale tuturor divizorilor lui n este egală cu n.  
 
  
   
    Exemple:    
 n = 6  
factori = {1, 2, 3, 6}  
n =phi(1) + phi(2) + phi(3) + phi(6)= 1 + 1 + 2 + 2 = 6n = 8factori = {1, 2, 4, 8}n =phi(1) + phi(2) + phi(4) + phi(8)= 1 + 1 + 2 + 4 = 8n = 10factori = {1, 2, 5, 10}n =phi(1) + phi(2) + phi(5) + phi(10)= 1 + 1 + 4 + 4 = 10
    6)    Cea mai faimoasă și importantă trăsătură este exprimată în        teorema lui Euler        :
 Teorema afirmă că dacă n și a sunt între prime  
atunci numere întregi pozitive (sau relativ prime).  
  
A^Φ(n)Φ 1 (mod n)
The  Criptosistem RSA  se bazează pe această teoremă:  
În cazul particular când m este prim să spunem p, teorema lui Euler se transformă în așa-numita        Mica teoremă a lui Fermat        :
 A^p-1Φ 1 (împotriva p)
     7)      Numărul de generatori ai unui grup ciclic finit sub adiție modulo n este Φ(n) .
     Articol înrudit:       
 Funcția Totient a lui Euler pentru toate numerele mai mici sau egale cu n    
 Funcția Euler Totient optimizată pentru evaluări multiple 
     Referinte:       
  http://e-maxx.ru/algo/euler_function   
  http://en.wikipedia.org/wiki/Euler%27s_totient_function  
   https://cp-algorithms.com/algebra/phi-function.html  
   http://mathcenter.oxford.memory.edu/site/math125/chineseRemainderTheorem/