ТОТІЕНТОВА ФУНКЦІЯ ЕЙЛЕРА - TECHCODEVIEW.COM

Функція Тотієнта Ейлера Φ(n) для вхідних даних n — це кількість чисел у {1, 2, 3, …, n-1}, які є взаємно простими з n, тобто чисел, НОД (найбільший спільний дільник) з n дорівнює 1.

Приклади:

Φ(1) = 1
gcd(1, 1) дорівнює 1

Φ(2) = 1
gcd(1, 2) дорівнює 1, але gcd(2, 2) дорівнює 2.

Φ(3) = 2
gcd(1, 3) дорівнює 1, а gcd(2, 3) дорівнює 1

Φ(4) = 2
gcd(1, 4) дорівнює 1, а gcd(3, 4) дорівнює 1

Φ(5) = 4
gcd(1, 5) дорівнює 1, gcd(2, 5) дорівнює 1,
gcd(3, 5) дорівнює 1, а gcd(4, 5) дорівнює 1

Φ(6) = 2
gcd(1, 6) дорівнює 1, а gcd(5, 6) дорівнює 1,

Рекомендована практика Функція Euler Totient Спробуйте!

Як обчислити Φ(n) для входу n?
А просте рішення полягає в переборі всіх чисел від 1 до n-1 і підрахунку чисел за допомогою gcd з n як 1. Нижче наведено реалізацію простого методу обчислення функції Totient Ейлера для вхідного цілого числа 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('<

Вихід

фі(1) = 1 фі(2) = 1 фі(3) = 2 фі(4) = 2 фі(5) = 4 фі(6) = 2 фі(7) = 6 фі(8) = 4 фі( 9) = 6 фі(10) = 4

Наведений вище код викликає функцію gcd O(n) разів. Часова складність функції gcd дорівнює O(h), де h — це кількість цифр у меншій кількості даних двох чисел. Таким чином, верхня межа на часова складність наведеного вище рішення дорівнює O(N^2 log N) [Як Φ може бути щонайбільше Log₁₀n цифр у всіх числах від 1 до n]

Допоміжний простір: O(log N)

Нижче a Краще рішення . Ідея базується на формулі добутку Ейлера, яка стверджує, що значення всіх функцій є нижчим від загального добутку простих множників p з n.

Формула в основному говорить, що значення Φ(n) дорівнює n, помноженому на побічний добуток (1 – 1/p) для всіх простих множників p з n. Наприклад, значення Φ(6) = 6 * (1-1/2) * (1 – 1/3) = 2.
Ми можемо знайти всі прості множники, використовуючи ідею, використану в це пост.

1) Ініціалізація: результат = n
2) Запустіть цикл від 'p' = 2 до sqrt(n), виконайте наступне для кожного 'p'.
а) Якщо p ділить n, то
Встановити: результат = результат * (1,0 - (1,0 / (float) p));
Розділіть усі входження p у n.
3) Повернути результат

substring_index в sql

Нижче наведено реалізацію формули добутку Ейлера.

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) результат -= результат / n;  //Оскільки в наборі {1,2,....,n-1} усі числа є взаємно простими з n //якщо n є простим числом return (int)result; } // Код драйвера int main() { int n;    для (n = 1; n<= 10; n++)  {  cout << 'Phi' << '('   << n << ')' << ' = '  << phi(n) <

 // 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) результат -= результат / n;  //Оскільки в наборі {1,2,....,n-1} усі числа є взаємно простими з n //якщо n є простим числом return (int)result; } // Програма драйвера для тестування вище function int main() { int n;  для (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) результат -= результат / n;  //Оскільки в наборі {1,2,....,n-1} усі числа є взаємно простими з n //якщо n є простим числом return (int)result;  } // Програма драйвера для перевірки вищевказаної функції public static void main(String args[]) { int n;  для (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 : результат -= результат // n #Оскільки в наборі {1,2,....,n-1} усі числа взаємно прості з n #якщо n є простим числом return int(result) # Драйвер програма для перевірки наведеної вище функції для n у діапазоні (1, 11) : print('phi(', n, ') = ', phi(n)) # Цей код надав # Нікіта Тіварі.>

 // 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) результат -= результат / n;  //Оскільки в наборі {1,2,....,n-1} усі числа є взаємно простими з n //якщо n є простим числом return (int)result;  } // Код драйвера public static void Main() { int n;  для (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) результат -= результат / n;  //Оскільки в наборі {1,2,....,n-1} усі числа є взаємно простими з n //якщо n є простим числом return parseInt(result); } // Код драйвера для (нехай 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) $результат -= $результат / $n;  //Оскільки в наборі {1,2,....,n-1} усі числа є взаємно простими з n //якщо n є простим числом return intval($result); } // Код драйвера для ($n = 1; $n<= 10; $n++) echo 'phi(' .$n. ') =' . phi($n).'
';   // This code is contributed by Sam007 Φ>>

Вихід

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 Фі(10) = 4

Часова складність: O(Φ n log n)
Допоміжний простір: О(1)

Ми можемо уникнути обчислень з плаваючою комою в наведеному вище методі. Ідея полягає в тому, щоб підрахувати всі прості множники та їх кратні та відняти цю кількість від n, щоб отримати значення функції totient (прості множники та кратні простим множникам не матимуть НОД як 1)

1) Ініціалізувати результат як n
2) Розглянемо кожне число 'p' (де 'p' змінюється від 2 до Φ(n)).
Якщо p ділить n, виконайте наступне
a) Відніміть усі кратні p від 1 до n [усі кратні p
матиме gcd більше 1 (принаймні p) з n]
б) Оновіть n, кілька разів поділивши його на p.
3) Якщо скорочене n більше 1, тоді вилучіть усі кратні
n із результату.

Нижче наведено реалізацію описаного вище алгоритму.

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) результат -= результат / n;    повернути результат; } // Код драйвера int main() { int n;  для (n = 1; n<= 10; n++)  {  cout << 'Phi' << '('   << n << ')' << ' = '  << phi(n) << endl;  }  return 0; } // This code is contributed by koulick_sadhu>

 // 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) результат -= результат / n;  повернути результат; } // Програма драйвера для тестування вище function int main() { int n;  для (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) результат -= результат / n;  повернути результат; } // Код драйвера public static void main (String[] args) { int n;  для (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): результат -= int(результат / n); повернути результат; # Код драйвера для n у діапазоні (1, 11): print('phi(',n,') =', phi(n)); # Цей код надано # mits>

 // 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) результат -= результат / n; повернути результат; } // Код драйвера static public void Main () { int n;  для (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) результат -= parseInt(результат / n);  повернути результат; } // Код драйвера для (нехай 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) $результат -= (int)$результат / $n;  повернути $результат; } // Код драйвера для ($n = 1; $n<= 10; $n++)  echo 'phi(', $n,') =',   phi($n), '
';   // This code is contributed  // by ajit Φ>>

Вихід

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 Фі(10) = 4

Часова складність: O(Φ n log n)
Допоміжний простір: О(1)

Розглянемо приклад, щоб зрозуміти наведений вище алгоритм.

java генерує випадкове число

n = 10.
Ініціалізація: результат = 10

2 є простим множником, тому n = n/i = 5, результат = 5
3 не є простим множником.

Цикл for зупиняється після 3, оскільки 4*4 не менше або дорівнює
до 10.

Після циклу for результат = 5, n = 5
Оскільки n> 1, результат = результат - результат/n = 4

Деякі цікаві властивості функції Ейлера

1) Для просте число p ,phi(p) = p – 1

Доказ:

phi(p) = p - 1, де p — будь-яке просте число. Ми це знаємоgcd(p, k) = 1де k будь-яке випадкове число іk eq pЗагальне число від 1 до p = p Число, для якогоgcd(p, k) = 1є1, тобто саме число p, тому віднімання 1 від pphi(p) = p - 1

Приклади:

phi(5) = 5 - 1 = 4phi(13) = 13 - 1 = 12phi(29) = 29 - 1 = 28

2) для два простих числа a і b phi(a cdot b) = phi(a) cdot phi(b) = (a – 1) cdot (b – 1) , використовується в Алгоритм RSA

Доказ:

phi(acdot b) = phi(a) cdot phi(b), де a і b — прості числаphi(a) = a - 1,phi(b) = b - 1Загальне число від 1 до ab = ab Загальне число, кратне a від 1 до ab =frac{a cdot b} {a}=bЗагальна кількість кратних b від 1 до ab =frac{a cdot b} {b}=a приклад: a = 5, b = 7, ab = 35, кратне a =frac {35} {5}= 7 {5, 10, 15, 20, 25, 30, 35}Кратні b =frac {35} {7}= 5 {7, 14, 21, 28, 35} Чи може бути подвійний рахунок? (уважно перегляньте приклад вище, спробуйте з іншим прості числа також для більшого розуміння) Звичайно, ми порахувалиab двічі у кратних a і b, отже, загальна кількість кратних = a + b - 1 (з якоюgcd eq 1зab)phi(ab) = ab - (a + b - 1), видаливши всі номери сgcd eq 1зab phi(ab) = a(b - 1) - (b - 1)phi(ab) = (a - 1) cdot (b - 1)phi(ab) = phi(a) cdot phi(b)

Приклади:

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) для просте число p ,phi(p ^ k) = p ^ k – p ^ {k – 1}

Доказ:

phi(p^k) = p ^ k - p ^{k - 1}, де p — просте числоЗагальна кількість чисел від 1 доp ^ k = p ^ kЗагальна кількість кратнихp = frac {p ^ k} {p} = p ^ {k - 1}Видалення цих кратних як з нимиgcd eq 1 приклад: p = 2, k = 5,p ^ k= 32Кратні 2 (як і з нимиgcd 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}

Приклади:

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) для два числа a і b phi(a cdot b) = phi(a) cdot phi(b) cdot frac {gcd(a, b)} {phi(gcd(a, b))}

Особливий випадок: gcd(a, b) = 1

phi(a cdot b) = phi(a) cdot phi(b) cdot frac {1} {phi(1)} = phi(a) cdot phi(b)

Приклади:

Особливий випадок: 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 Нормальний випадок: 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) Сума значень функцій всіх дільників числа n дорівнює n.

гауссс

Приклади:

n = 6
фактори = {1, 2, 3, 6}
n =phi(1) + phi(2) + phi(3) + phi(6)= 1 + 1 + 2 + 2 = 6n = 8факторів = {1, 2, 4, 8}n =phi(1) + phi(2) + phi(4) + phi(8)= 1 + 1 + 2 + 4 = 8n = 10факторів = {1, 2, 5, 10}n =phi(1) + phi(2) + phi(5) + phi(10)= 1 + 1 + 4 + 4 = 10

6) Найбільш відома і важлива особливість виражається в Теорема Ейлера :

Теорема стверджує, що якщо n і a є взаємно простими
(або взаємно прості) додатні цілі числа, тоді

a^Φ(n)Φ 1 (mod n)

The Криптосистема RSA базується на цій теоремі:
У конкретному випадку, коли m є простим числом, наприклад p, теорема Ейлера перетворюється на так звану Маленька теорема Ферма :

a^р-1Φ 1 (проти p)

вовк проти лисиці

7) Кількість твірних скінченної циклічної групи при додаванні за модулем n дорівнює Φ(n) .

Пов'язана стаття:
Функція Totient Ейлера для всіх чисел, менших або рівних n
Оптимізована функція Euler Totient для кількох оцінок

Література:
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

Функція Ейлера

Деякі цікаві властивості функції Ейлера