In number theory, Euler’s totient function, also be called Euler’s phi function \( \varphi(n) \) counts the positive integers up to a given integer n that are relatively prime to n.
\( \varphi(1)=1 \)
\( \varphi(mn)=\varphi(m)\varphi(n) \hspace{16 pt} whenever \hspace {8pt} m \bot n \hspace {8pt} i.e. \hspace {8pt} gcd(m, n)=1 \)
Si sint A et B numeri inter se primi et numerus partium ad A primarum sit = a, numerus vero partium ad B primarum sit = b, tum numerus partium ad productum AB primarum erit = ab. - L. Euler
Outline of proof: let A, B, C be the sets of nonnegative integers, which are, respectively, coprime to and less than m, n, and mn; then there is a bijection between A × B and C, by the Chinese remainder theorem.
Concrete Mathematics p146
4 Number Theory
4.9 PHI AND MU
If \( m \gt 1 \) is not a prime power, we can write \( m = m1 \times m2 \) where \( m1 \bot m2 \).
Then the numbers \( 0 \leq n \lt m \) can be represented in a residue number system as \( (n \hspace{1mm} mod \hspace{1mm} m1, n \hspace{1mm} mod \hspace{1mm} m2) \). We have
\( \hspace{4mm} n \bot m \hspace{8mm} \Longleftrightarrow \hspace{8mm} n \hspace{1mm} mod \hspace{1mm} m1 \hspace{4mm} \bot \hspace{4mm} m1 \hspace{4mm} and \hspace{4mm} n \hspace{1mm} mod \hspace{1mm} m2 \hspace{4mm} \bot \hspace{4mm} m2 \)
Hence, \( n \hspace{1mm} mod \hspace{1mm} m \) is “good” if and only if \( n \hspace{1mm} mod \hspace{1mm} m1 \) and \( n \hspace{1mm} mod \hspace{1mm} m2 \) are both “good,” if we consider relative primality to be a virtue. The total number of good values modulo m can now be computed, recursively: It is \( \varphi(m1)\varphi(m2) \), because there are \( \varphi(m1) \) good ways to choose the first component \( n \hspace{1mm} mod \hspace{1mm} m1 \) and \( \varphi(m2) \) good ways to choose the second component \( n \hspace{1mm} mod \hspace{1mm} m2 \) in the residue representation.
Concrete Mathematics p144
NUMBER THEORY - Exercises - Warmups - 10 Compute \( \phi(999) \).
\( \phi(p)=p-1 \)
\( \phi(p^k)=p^k-p^{k-1} \)
\( \phi(999)=\phi(3^3 \times 37) \)
\( =\phi(3^3) \times \phi(37) = (3^3-3^2) \times 36 = 648 \)
\( \phi(666) = 216 = 6 \times 6 \times 6 \)
- Euler’s Phi Function and the Chinese Remainder Theorem
- Computing the Euler totient function, part 1
- Computing the Euler totient function, part 2: seeing phi is multiplicative
- Computing the Euler totient function, part 3: proving phi is multiplicative
- Computing the Euler totient function, part 4: totient of prime powers
- Euler’s totient function