- galois.euler_phi(n: int) int
Counts the positive integers (totatives) in
that are coprime to .See also
Notes¶
This function implements the Euler totient function
for prime
and the prime factorization .References¶
Section 2.4.1 from https://cacr.uwaterloo.ca/hac/about/chap2.pdf
Examples¶
Compute
.In [1]: n = 20 In [2]: phi = galois.euler_phi(n); phi Out[2]: 8
Find the totatives that are coprime with
. The number of totatives of is .In [3]: x = galois.totatives(n); x Out[3]: [1, 3, 7, 9, 11, 13, 17, 19] In [4]: len(x) == phi Out[4]: True
For prime
, .In [5]: n = 13 In [6]: galois.euler_phi(n) Out[6]: 12