Eulerio totieno funkcija Φ(n) įvesties n yra skaičių {1, 2, 3, …, n-1}, kurie yra santykinai pirminiai n, skaičius, t. y. skaičiai, kurių GCD (Didžiausias bendras daliklis) su n yra 1.
Pavyzdžiai:
Φ(1) = 1
gcd(1, 1) yra 1
Φ(2) = 1
gcd(1, 2) yra 1, bet gcd(2, 2) yra 2.
Φ(3) = 2
gcd(1, 3) yra 1, o gcd(2, 3) yra 1
Φ(4) = 2
gcd(1, 4) yra 1, o gcd(3, 4) yra 1
Φ(5) = 4
gcd(1, 5) yra 1, gcd(2, 5) yra 1,
gcd(3, 5) yra 1, o gcd(4, 5) yra 1
Φ(6) = 2
gcd(1, 6) yra 1, o gcd(5, 6) yra 1,
Kaip apskaičiuoti Φ(n) įvesties n?
A paprastas sprendimas yra kartoti visus skaičius nuo 1 iki n-1 ir suskaičiuoti skaičius, kai gcd yra n kaip 1. Toliau pateikiamas paprastas metodas, skirtas apskaičiuoti Eulerio totieno funkciją įvesties sveikajam skaičiui 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>C# // 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('<
Išvestis 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
rūšiuoti masyvų sąrašą java
Aukščiau pateiktas kodas iškviečia gcd funkciją O(n) kartus. Gcd funkcijos laiko sudėtingumas yra O(h), kur h yra skaitmenų skaičius mažesniame duotų dviejų skaičių skaičiuje. Todėl viršutinė riba ant laiko sudėtingumas aukščiau pateikto sprendinio yra O(N^2 log N) [Kaip Φ gali būti daugiausia Log10n skaitmenų visuose skaičiuose nuo 1 iki n]
Pagalbinė erdvė: O(log N)
Žemiau yra a Geresnis Sprendimas . Idėja grindžiama Eulerio produkto formule, kuri teigia, kad visų funkcijų reikšmė yra mažesnė už bendruosius produkto pirminius veiksnius p iš n.
Iš esmės formulė sako, kad Φ(n) reikšmė yra lygi n, padaugintam iš (1 – 1/p) šalutinio produkto, visų n pirminių faktorių p. Pavyzdžiui, Φ(6) reikšmė = 6 * (1-1/2) * (1 – 1/3) = 2.
Visus pagrindinius veiksnius galime rasti naudodami panaudotą idėją tai paštu.
1) Inicijuoti : rezultatas = n
2) Vykdykite ciklą nuo 'p' = 2 iki sqrt(n), atlikite kiekvieną 'p'.
a) Jei p dalijasi n, tai
Rinkinys: rezultatas = rezultatas * (1,0 - (1,0 / (plūduriuoti) p));
Visus p atvejus padalinkite į n.
3) Grąžinimo rezultatas
Žemiau pateikiama Eulerio produkto formulės įgyvendinimas.
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) rezultatas -= rezultatas / n; //Kadangi aibėje {1,2,....,n-1}, visi skaičiai yra santykinai pirminiai su n //jei n yra pirminis skaičius, grąžinamas (int) rezultatas; } // Tvarkyklės kodas 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) rezultatas -= rezultatas / n; //Kadangi aibėje {1,2,....,n-1}, visi skaičiai yra santykinai pirminiai su n //jei n yra pirminis skaičius, grąžinamas (int) rezultatas; } // Tvarkyklės programa, skirta patikrinti aukščiau pateiktą funkciją int main() { int n; už (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) rezultatas -= rezultatas / n; //Kadangi aibėje {1,2,....,n-1}, visi skaičiai yra santykinai pirminiai su n //jei n yra pirminis skaičius, grąžinamas (int) rezultatas; } // Tvarkyklės programa, skirta patikrinti aukščiau pateiktą funkciją public static void main(String args[]) { int n; už (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 : rezultatas -= rezultatas // n #Kadangi aibėje {1,2,....,n-1}, visi skaičiai yra santykinai pirminiai su n #jei n yra pirminis skaičius return int(result) # Vairuotojas programa, skirta išbandyti aukščiau esančią n funkciją diapazone (1, 11): print('phi(', n, ') = ', phi(n)) # Šį kodą pateikė # 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) rezultatas -= rezultatas / n; //Kadangi aibėje {1,2,....,n-1}, visi skaičiai yra santykinai pirminiai su n //jei n yra pirminis skaičius, grąžinamas (int) rezultatas; } // Vairuotojo kodas public static void Main() { int n; už (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) rezultatas -= rezultatas / n; //Kadangi aibėje {1,2,....,n-1}, visi skaičiai yra santykinai pirminiai su n //jei n yra pirminis skaičius return parseInt(result); } // Tvarkyklės kodas (tegul 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) $rezultatas -= $rezultatas / $n; //Kadangi aibėje {1,2,....,n-1}, visi skaičiai yra santykinai pirminiai su n //jei n yra pirminis skaičius return intval($result); } // Tvarkyklės kodas ($n = 1; $n<= 10; $n++) echo 'phi(' .$n. ') =' . phi($n).'
'; // This code is contributed by Sam007 Φ>>>
Išvestis 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
Laiko sudėtingumas: O(Φ n log n)
Pagalbinė erdvė: O(1)
Aukščiau pateiktu metodu galime išvengti slankiojo kablelio skaičiavimų. Idėja yra suskaičiuoti visus pirminius veiksnius ir jų kartotinius ir atimti šį skaičių iš n, kad gautumėte visos funkcijos reikšmę (pirminiai veiksniai ir pirminių veiksnių kartotiniai neturės gcd kaip 1)
1) Inicijuoti rezultatą kaip n
2) Apsvarstykite kiekvieną skaičių „p“ (kur „p“ kinta nuo 2 iki Φ(n)).
Jei p dalija n, atlikite šiuos veiksmus
a) Iš 1 atimkite visus p kartotinius [visi p kartotiniai
turės gcd daugiau nei 1 (bent p) su n]
b) Atnaujinkite n, pakartotinai dalydami jį iš p.
3) Jei sumažintas n yra didesnis nei 1, tada pašalinkite visus kartotinius
n iš rezultato.
Žemiau pateikiamas aukščiau pateikto algoritmo įgyvendinimas.
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) rezultatas -= rezultatas / n; grąžinti rezultatą; } // Tvarkyklės kodas 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) rezultatas -= rezultatas / n; grąžinti rezultatą; } // Tvarkyklės programa, skirta patikrinti aukščiau pateiktą funkciją int main() { int n; už (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) rezultatas -= rezultatas / n; grąžinti rezultatą; } // Tvarkyklės kodas public static void main (String[] args) { int n; už (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): rezultatas -= int(rezultatas / n); grąžinti rezultatą; # Tvarkyklės kodas n diapazone (1, 11): print('phi(',n,') =', phi(n)); # Šį kodą # pateikė 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) rezultatas -= rezultatas / n; grąžinti rezultatą; } // Vairuotojo kodas static public void Pagrindinis () { int n; už (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) rezultatas -= parseInt(result / n); grąžinti rezultatą; } // Tvarkyklės kodas (tegul 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) $rezultatas -= (int)$rezultatas / $n; grąžinti $rezultatą; } // Tvarkyklės kodas ($n = 1; $n<= 10; $n++) echo 'phi(', $n,') =', phi($n), '
'; // This code is contributed // by ajit Φ>>>
Išvestis 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
Laiko sudėtingumas: O(Φ n log n)
Pagalbinė erdvė: O(1)
Paimkime pavyzdį, kad suprastume aukščiau pateiktą algoritmą.
sąrašai java
n = 10.
Inicijuoti: rezultatas = 10
2 yra pirminis koeficientas, taigi n = n/i = 5, rezultatas = 5
3 nėra pagrindinis veiksnys.
For ciklo sustoja po 3, nes 4*4 yra ne mažesnis arba lygus
iki 10.
Po for ciklo rezultatas = 5, n = 5
Kadangi n> 1, rezultatas = rezultatas - rezultatas/n = 4
Rajeshas Khanna
Kai kurios įdomios Eulerio Totient funkcijos ypatybės
1) Dėl pirminis skaičius p ,phi(p) = p – 1
Įrodymas:
kur k yra bet koks atsitiktinis skaičius irBendras skaičius nuo 1 iki p = p Skaičius, kuriam, ty pats skaičius p, todėl iš p atimant 1phi(p) = p - 1
Pavyzdžiai:
phi(5) = 5 - 1 = 4 phi(13) = 13 - 1 = 12 phi(29) = 29 - 1 = 28
2) Dėl du pirminiai skaičiai a ir b phi(a cdot b) = phi(a) cdot phi(b) = (a – 1) cdot (b – 1) , naudojamas RSA algoritmas
Įrodymas:
phi(acdot b) = phi(a) cdot phi(b) , kur a ir b yra pirminiai skaičiaiphi(a) = a - 1 ,phi(b) = b - 1 frac{a cdot b} {a} =b Bendri b kartotiniai nuo 1 iki ab =frac{a cdot b} {b} =a Pavyzdys: a = 5, b = 7, ab = 35 a = kartotiniaifrac {35} {5} = 7 {5, 10, 15, 20, 25, 30, 35}b kartotiniai =frac {35} {7} = 5 {7, 14, 21, 28, 35}ab du kartus a kartotiniuose ir b kartotiniuose, taigi, iš viso kartotiniai = a + b - 1 (su kuriaisgcd
eq 1 suab )phi(ab) = ab - (a + b - 1) , pašalinant visus numerius sugcd
eq 1 suab phi(ab) = a(b - 1) - (b - 1) phi(ab) = (a - 1) cdot (b - 1) phi(ab) = phi(a) cdot phi(b)
Pavyzdžiai:
phi(5 cdot 7) = phi(5) cdot phi(7) = (5 - 1) cdot (7 - 1) = 24 phi(3 cdot 5) = phi(3) cdot phi(5) = (3 - 1) cdot (5 - 1) = 8 phi(3 cdot 7) = phi(3) cdot phi(7) = (3 - 1) cdot (7 - 1) = 12
3) Dėl pirminis skaičius p ,phi(p ^ k) = p ^ k – p ^ {k – 1}
aktorius ranbir kapoor amžiaus
Įrodymas:
phi(p^k) = p ^ k - p ^{k - 1} , kur p yra pirminis skaičiusp ^ k = p ^ k Iš viso kartotiniaip = frac {p ^ k} {p} = p ^ {k - 1} Pašalinkite šiuos kartotinius kaip ir su jaisgcd
eq 1 p ^ k = 32 Pakartotiniai iš 2 (kaip ir su jaisgcd
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}
Pavyzdžiai:
phi(2 ^ 5) = 2 ^ 5 - 2 ^ {5 - 1} = 32 - 16 = 16 phi(5 ^ 3) = 5 ^ 3 - 5 ^ {3 - 1} = 125 - 25 = 100 phi(3 ^ 5) = 3 ^ 5 - 3 ^ {5 - 1} = 243 - 81 = 162
4) Dėl du skaičiai a ir b phi(a cdot b) = phi(a) cdot phi(b) cdot frac {gcd(a, b)} {phi(gcd(a, b))}
Ypatingas atvejis: gcd(a, b) = 1
phi(a cdot b) = phi(a) cdot phi(b) cdot frac {1} {phi(1)} = phi(a) cdot phi(b)
Pavyzdžiai:
Ypatinga byla : 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 = 6 phi(8 cdot 9) = phi(8) cdot phi(9) = 4 cdot 6 = 24 phi(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 = 8 phi(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 = 16 phi(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) Visų n daliklių visų funkcijų reikšmių suma lygi n.
Pavyzdžiai:
n = 6
faktoriai = {1, 2, 3, 6}
n =phi(1) + phi(2) + phi(3) + phi(6) = 1 + 1 + 2 + 2 = 6phi(1) + phi(2) + phi(4) + phi(8) = 1 + 1 + 2 + 4 = 8phi(1) + phi(2) + phi(5) + phi(10) = 1 + 1 + 4 + 4 = 10
ne
6) Žymiausia ir svarbiausia savybė išreikšta Eulerio teorema :
Teorema teigia, kad jei n ir a yra koprime
(arba santykinai pirminiai) teigiami sveikieji skaičiai
aΦ(n)Φ 1 (mod. n)
The RSA kriptosistema remiasi šia teorema:
Konkrečiu atveju, kai m yra pirminis tarkim p, Eulerio teorema virsta vadinamąja Mažoji Ferma teorema :
ap-1Φ 1 (prieš p)
7) Baigtinės ciklinės grupės generatorių skaičius pridedant modulį yra Φ(n) .
Susijęs straipsnis:
Eulerio totieno funkcija visiems skaičiams, mažesniems arba lygiems n
Optimizuota „Euler Totient“ funkcija keliems vertinimams
Nuorodos:
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/
