Difference between revisions of "Euler totient"
m (Tom moved page Totient function to Euler phi) |
|||
| Line 1: | Line 1: | ||
| − | Euler's | + | Euler's $\phi$ function (sometimes called the "totient" function) is the function <br /> |
<center>$\phi(n) =$ # of positive integers $\leq n$ that are relatively prime to $n$.</center> | <center>$\phi(n) =$ # of positive integers $\leq n$ that are relatively prime to $n$.</center> | ||
Revision as of 11:53, 19 January 2015
Euler's $\phi$ function (sometimes called the "totient" function) is the function
Properties
Theorem: The function $\phi$ obeys the formula $$\phi(n) = \displaystyle\sum_{d|n} \mu(d) \dfrac{n}{d},$$ where the notation $d | n$ indicates that $d$ is a divisor of $n$ and $\mu$ is the Möbius function.
Proof: █
Theorem: The function $\phi$ obeys the formula $$\phi(n) = n \displaystyle\prod_{p | n} \left( 1 - \dfrac{1}{p} \right),$$ where the notation $p | n$ indicates that $p$ is a prime that divides $n$.
Proof: █
Theorem: The following formula holds: $$\phi(n) = n\lim_{s \rightarrow 1} \zeta(s) \displaystyle\sum_{d | n} \mu(d)(e^{\frac{1}{d}})^{s-1},$$ where $\zeta$ is the Riemann zeta function and \mu is the Möbius function, $e$ is the base of the exponential and the notation $d|n$ indicates that $d$ is any divisor of $n$.
Proof: █
