Difference between revisions of "Euler totient"
From specialfunctionswiki
(Created page with "Euler's totient function (sometimes called Euler's $\phi$ function) is the function <br /> <center>$\phi(n) =$ # of positive integers $\leq n$ that are relatively prime to $n$...") |
|||
| Line 1: | Line 1: | ||
Euler's totient function (sometimes called Euler's $\phi$ function) is the function <br /> | Euler's totient function (sometimes called Euler's $\phi$ 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> | ||
| + | |||
| + | =Properties= | ||
| + | <div class="toccolours mw-collapsible mw-collapsed" style="width:800px"> | ||
| + | <strong>Theorem:</strong> 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$. | ||
| + | <div class="mw-collapsible-content"> | ||
| + | <strong>Proof:</strong> proof goes here █ | ||
| + | </div> | ||
| + | </div> | ||
Revision as of 15:58, 4 October 2014
Euler's totient function (sometimes called Euler's $\phi$ function) is the function
Properties
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: proof goes here █
