Euler totient

From specialfunctionswiki
Revision as of 18:48, 24 May 2016 by Tom (talk | contribs)
Jump to: navigation, search

Euler's totient function is the function

$\phi(n) =$ # of positive integers $\leq n$ that are relatively prime to $n$.

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:

Videos

Euler's Totient Function: what it is and how it works
Euler's Totient Theorem: What is Euler's Totient Theorem and Why is it useful?
Euler's Totient Function | How To Find Totient Of A Number Using Euler's Product Formula
Euler's Totient Function
Euler's totient function
Prime Factorisation and Euler Totient Function Part 14
Application of Euler Totient Function Part 16
Möbius and Euler totient functions
Euler Totient Theorem, Fermat Little Theorems
Euler's Phi Function
03 Modern cryptography 08 Euler's totient function

References

Abramowitz&Stegun