EILERA KOPĪGĀ FUNKCIJA — TECHCODEVIEW.COM

Eilera kopējā funkcija Φ(n) ievadei n ir skaitļu skaits {1, 2, 3, …, n-1}, kas ir relatīvi pirmskaitļi pret n, t.i., skaitļi, kuru GCD (lielākais kopīgais dalītājs) ar n ir 1.

Piemēri:

Φ(1) = 1
gcd(1, 1) ir 1

Φ(2) = 1
gcd(1, 2) ir 1, bet gcd(2, 2) ir 2.

Φ(3) = 2
gcd(1, 3) ir 1 un gcd(2, 3) ir 1

Φ(4) = 2
gcd(1, 4) ir 1 un gcd(3, 4) ir 1

Φ(5) = 4
gcd(1, 5) ir 1, gcd(2, 5) ir 1,
gcd(3, 5) ir 1 un gcd(4, 5) ir 1

Φ(6) = 2
gcd(1, 6) ir 1 un gcd(5, 6) ir 1,

Ieteicamā prakse Euler Totient funkcija Izmēģiniet to!

Kā aprēķināt Φ(n) ievadei n?
A vienkāršs risinājums ir atkārtot visus skaitļus no 1 līdz n-1 un saskaitīt skaitļus ar gcd ar n kā 1. Tālāk ir sniegta vienkāršās metodes ieviešana, lai aprēķinātu Eilera Totient funkciju ievades veselam skaitlim 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('<  
  Izvade  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
 
 

   
Iepriekš minētais kods izsauc gcd funkciju O(n) reizes. Funkcijas gcd laika sarežģītība ir O(h), kur h ir ciparu skaits mazākā doto divu skaitļu skaitā. Tāpēc ir noteikta augšējā robeža      laika sarežģītība      no iepriekš minētā risinājuma ir O(N^2 log N) [Kā Φ var būt ne vairāk kā Log₁₀n cipari visos skaitļos no 1 līdz n]
       Palīgtelpa:      O(log N)
   
Zemāk ir a    Labāks Risinājums    . Ideja ir balstīta uz Eilera produkta formulu, kas nosaka, ka visu funkciju vērtība ir zemāka par produkta vispārējiem galvenajiem faktoriem p no n.
 
 

 
 Formula pamatā saka, ka Φ(n) vērtība ir vienāda ar n, kas reizināta ar (1 – 1/p) blakusproduktu visiem n primārajiem faktoriem p. Piemēram, vērtība Φ(6) = 6 * (1-1/2) * (1 - 1/3) = 2.  
Mēs varam atrast visus galvenos faktorus, izmantojot izmantoto ideju šis pastu.
 1) Inicializēt: rezultāts = n  
2) Palaidiet cilpu no 'p' = 2 līdz sqrt(n), veiciet šādas darbības katram 'p'.  
a) Ja p dala n, tad  
Komplekts: rezultāts = rezultāts * (1,0 - (1,0 / (peld) p));  
Sadaliet visus p gadījumus ar n.  
3) Atgriešanas rezultāts
  
Zemāk ir Eulera produkta formulas ieviešana.
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) rezultāts -= rezultāts / n;  //Tā kā kopā {1,2,....,n-1} visi skaitļi ir relatīvi pirmskaitļi ar n //ja n ir pirmskaitļa atgriešanas (int) rezultāts; } // Draivera kods int main() { int n;    for(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) rezultāts -= rezultāts / n;  //Tā kā kopā {1,2,....,n-1} visi skaitļi ir relatīvi pirmskaitļi ar n //ja n ir pirmskaitļa atgriešanas (int) rezultāts; } // Draivera programma, lai pārbaudītu iepriekš minēto funkciju int main() { int n;  par (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) rezultāts -= rezultāts / n;  //Tā kā kopā {1,2,....,n-1} visi skaitļi ir relatīvi pirmskaitļi ar n //ja n ir pirmskaitļa atgriešanas (int) rezultāts;  } // Draivera programma, lai pārbaudītu iepriekš minēto funkciju public static void main(String args[]) { int n;  par (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 : rezultāts -= rezultāts // n #Tā kā kopā {1,2,....,n-1} visi skaitļi ir relatīvi pirmskaitļi ar n #ja n ir pirmskaitlis, atgriež int(rezultāts) # Draiveris programma, lai pārbaudītu iepriekšminēto funkciju n diapazonā (1, 11): print('phi(', n, ') = ', phi(n)) # Šo kodu # sniedza 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) rezultāts -= rezultāts / n;  //Tā kā kopā {1,2,....,n-1} visi skaitļi ir relatīvi pirmskaitļi ar n //ja n ir pirmskaitļa atgriešanas (int) rezultāts;  } // Vadītāja kods public static void Main() { int n;  par (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) rezultāts -= rezultāts / n;  //Tā kā kopā {1,2,....,n-1} visi skaitļi ir relatīvi pirmskaitļi ar n //ja n ir pirmskaitlis, atgriež parseInt(rezultāts); } // Draiveris kods (lai 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) $rezultāts -= $rezultāts / $n;  //Tā kā kopā {1,2,....,n-1} visi skaitļi ir relatīvi pirmskaitļi ar n //ja n ir pirmskaitlis return intval($rezultāts); } // Draivera kods ($n = 1; $n<= 10; $n++) echo 'phi(' .$n. ') =' . phi($n).'
';   // This code is contributed by Sam007 Φ>>>  
  Izvade  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
     Laika sarežģītība:    O(Φ n log n)  
    Palīgtelpa:    O(1)
 Iepriekš minētajā metodē mēs varam izvairīties no peldošā komata aprēķiniem. Ideja ir saskaitīt visus primāros faktorus un to daudzkārtņus un atņemt šo skaitu no n, lai iegūtu visas funkcijas vērtību (sākotnējo faktoru un primāro faktoru daudzkārtņu gcd nebūs 1)
 1) Inicializējiet rezultātu kā n  
2) Apsveriet katru skaitli 'p' (kur 'p' mainās no 2 līdz Φ(n)).  
Ja p dala n, rīkojieties šādi  
a) Atņemiet visus p daudzkārtņus no 1 līdz n [visi p daudzkārtņi  
būs gcd vairāk nekā 1 (vismaz p) ar n]  
b) Atjauniniet n, atkārtoti dalot to ar p.  
3) Ja samazinātais n ir lielāks par 1, tad noņemiet visus reizinātājus  
no n no rezultāta.
Zemāk ir aprakstīta iepriekš minētā algoritma ieviešana.
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) rezultāts -= rezultāts / n;    atgriešanās rezultāts; } // Draivera kods int main() { int n;  for(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) rezultāts -= rezultāts / n;  atgriešanās rezultāts; } // Draivera programma, lai pārbaudītu iepriekš minēto funkciju int main() { int n;  par (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) rezultāts -= rezultāts / n;  atgriešanās rezultāts; } // Draivera kods public static void main (String[] args) { int n;  par (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): rezultāts -= int(rezultāts / n); atgriešanās rezultāts; # Draivera kods n diapazonā (1, 11): print('phi(',n,') =', phi(n)); # Šo kodu # sniedza 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) rezultāts -= rezultāts / n; atgriešanās rezultāts; } // Vadītāja kods static public void Galvenā () { int n;  par (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) rezultāts -= parseInt(rezultāts / n);  atgriešanās rezultāts; } // Draivera kods (lai 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) $rezultāts -= (int)$rezultāts / $n;  atgriezt $rezultātu; } // Draivera kods ($n = 1; $n<= 10; $n++)  echo 'phi(', $n,') =',   phi($n), '
';   // This code is contributed  // by ajit Φ>>>  
  Izvade  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
     Laika sarežģītība:    O(Φ n log n)  
    Palīgtelpa:    O(1)
 Ņemsim piemēru, lai saprastu iepriekš minēto algoritmu.
 n = 10.  
Inicializēt: rezultāts = 10  
  
2 ir galvenais koeficients, tāpēc n = n/i = 5, rezultāts = 5  
3 nav galvenais faktors.  
  
For cilpa apstājas pēc 3, jo 4*4 nav mazāka vai vienāda  
līdz 10.  
  
Pēc for cilpas rezultāts = 5, n = 5  
Tā kā n> 1, rezultāts = rezultāts - rezultāts/n = 4
    Dažas interesantas Eilera Totient funkcijas īpašības       
    1)    Priekš    pirmskaitlis lpp    ,phi(p) = p – 1
     Pierādījums:    
 kur k ir jebkurš nejaušs skaitlis unKopējais skaitlis no 1 līdz p = p Skaitlis, kuram    Piemēri:     
 phi(5) = 5 - 1 = 4phi(13) = 13 - 1 = 12phi(29) = 29 - 1 = 28
  
    2)    Priekš    divi pirmskaitļi a un b     phi(a cdot b) = phi(a) cdot phi(b) = (a – 1) cdot (b – 1) , lietots  RSA algoritms  
     Pierādījums:    
 phi(acdot b) = phi(a) cdot phi(b), kur a un b ir pirmskaitļiphi(a) = a - 1,phi(b) = b - 1Kopējais skaitlis no 1 līdz ab = a Kopējie daudzkārtņi no 1 līdz ab =frac{a cdot b} {a}=bKopējie b daudzkārtņi no 1 līdz ab =frac{a cdot b} {b}=a    Piemērs:    a = 5, b = 7, ab = 35 A = daudzkārtņifrac {35} {5}= 7 {5, 10, 15, 20, 25, 30, 35}b reizes =frac {35} {7}= 5 {7, 14, 21, 28, 35}    Vai var būt dubultā uzskaite?    (uzmanīgi skatieties iepriekš minēto piemēru, mēģiniet ar citiem    pirmskaitļi    arī labākai izpratnei)Protams, mēs esam skaitījušiab     divreiz    a reizinātā un b reizinātā, tātad, kopējie reizinātāji = a + b - 1 (ar kogcd 
eq 1arab)phi(ab) = ab - (a + b - 1), noņemot visus numurus argcd 
eq 1arab phi(ab) = a(b - 1) - (b - 1)phi(ab) = (a - 1) cdot (b - 1)phi(ab) = phi(a) cdot phi(b)
    Piemēri:    
 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)    Priekš    pirmskaitlis lpp    ,phi(p ^ k) = p ^ k – p ^ {k – 1}
     Pierādījums:    
 phi(p^k) = p ^ k - p ^{k - 1}, kur p ir pirmskaitlisKopējie skaitļi no 1 līdzp ^ k = p ^ kKopējie daudzkārtņip = frac {p ^ k} {p} = p ^ {k - 1}Šo reizinātāju noņemšana tāpat kā ar tiemgcd 
eq 1    Piemērs :    p = 2, k = 5,p ^ k= 32 reizinātāji no 2 (kā ar tiemgcd 
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}
    Piemēri:    
 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)    Priekš    divi cipari a un b     phi(a cdot b)  = phi(a) cdot phi(b)  cdot frac {gcd(a, b)} {phi(gcd(a, b))}
     Īpašs gadījums: gcd(a, b) = 1    
 phi(a cdot b) = phi(a) cdot phi(b) cdot frac {1} {phi(1)} = phi(a) cdot phi(b)
     Piemēri:    
     Īpašs gadījums :    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     Parastais gadījums:    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)    Visu n dalītāju kopējo funkciju vērtību summa ir vienāda ar n.  
 
  
   
    Piemēri:    
 n = 6  
faktori = {1, 2, 3, 6}  
n =phi(1) + phi(2) + phi(3) + phi(6)= 1 + 1 + 2 + 2 = 6n = 8 faktori = {1, 2, 4, 8} n =phi(1) + phi(2) + phi(4) + phi(8)= 1 + 1 + 2 + 4 = 8n = 10 faktori = {1, 2, 5, 10} n =phi(1) + phi(2) + phi(5) + phi(10)= 1 + 1 + 4 + 4 = 10
    6)    Slavenākā un svarīgākā iezīme ir izteikta        Eilera teorēma        :
java nomaiņa
 Teorēma nosaka, ka, ja n un a ir koprime  
(vai salīdzinoši pirmie) pozitīvi veseli skaitļi, tad  
  
a^Φ(n)Φ 1 (mod n)
The  RSA kriptosistēma  ir balstīta uz šo teorēmu:  
Konkrētajā gadījumā, kad m ir galvenais, teiksim p, Eilera teorēma pārvēršas par tā saukto        Fermā mazā teorēma        :
 a^p-1Φ 1 (pret p)
     7)      Galīgas cikliskās grupas ģeneratoru skaits, kas tiek pievienoti moduļiem, ir Φ(n) .
     Saistīts raksts:       
 Eilera Totient funkcija visiem skaitļiem, kas ir mazāki vai vienādi ar n    
 Optimizēta Euler Totient funkcija vairākiem novērtējumiem 
     Atsauces:       
  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/

TechCodeview

Eilera Totienta funkcija

Dažas interesantas Eilera Totient funkcijas īpašības