Difference between revisions of "Euler's totient function"
Jump to navigation
Jump to search
JamesWilson (talk | contribs) (cat) |
DavidB4-bot (talk | contribs) (→Some properties of the totient function: clean up & uniformity) |
||
| (One intermediate revision by one other user not shown) | |||
| Line 2: | Line 2: | ||
:<math>\varphi \left( p_1^{k_1} \cdots p_n^{k_n} \right) = (p_1-1)p_1^{k_1-1} \cdot \cdots \cdot (p_n-1)p_n^{k_n-1}</math>. | :<math>\varphi \left( p_1^{k_1} \cdots p_n^{k_n} \right) = (p_1-1)p_1^{k_1-1} \cdot \cdots \cdot (p_n-1)p_n^{k_n-1}</math>. | ||
| − | + | == Some properties of the totient function == | |
* For a prime number <math>p</math>, all numbers less than <math>p</math> are coprime to it, so <math>\varphi(p) = p -1</math>. | * For a prime number <math>p</math>, all numbers less than <math>p</math> are coprime to it, so <math>\varphi(p) = p -1</math>. | ||
* For every <math>n</math>, <math>\varphi(n) \leq n-1</math>. This is because there are only <math>n-1</math> numbers less than <math>n</math>. | * For every <math>n</math>, <math>\varphi(n) \leq n-1</math>. This is because there are only <math>n-1</math> numbers less than <math>n</math>. | ||
| Line 8: | Line 8: | ||
* A sharper bound is | * A sharper bound is | ||
::<math>\varphi(n) > \frac{n}{e^\gamma \log \log n + \frac{3}{\log \log n}}</math> | ::<math>\varphi(n) > \frac{n}{e^\gamma \log \log n + \frac{3}{\log \log n}}</math> | ||
| − | * How fast does the totient function grow? For large <math>n</math>, <math>\phi(n) \approx n</math> "on average". One way to make this precise is by stating <math> \frac{1}{n^2} \sum_{k=1}^n \varphi(k) = \frac{3}{\pi^2} + O \left( \frac{\log n}{n} \right)</math>, while in contrast <math> \frac{1}{n^2} \sum_{k=1}^n k = \frac{1}{2} + O \left( \frac{1}{n} \right). | + | * How fast does the totient function grow? For large <math>n</math>, <math>\phi(n) \approx n</math> "on average". One way to make this precise is by stating <math> \frac{1}{n^2} \sum_{k=1}^n \varphi(k) = \frac{3}{\pi^2} + O \left( \frac{\log n}{n} \right)</math>, while in contrast <math> \frac{1}{n^2} \sum_{k=1}^n k = \frac{1}{2} + O \left( \frac{1}{n} \right).</math> |
[[Category:Mathematics]] | [[Category:Mathematics]] | ||
Latest revision as of 12:12, July 13, 2016
The totient function Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varphi} of a positive integer is the number of integers less than which have no factors in common with (i.e. such that the greatest common divisor of and is 1). For example, the numbers 1, 5, 7, and 11 have no factors in common with 12, so . The totient function can be computer from a prime factorization of using the formula
- .
Some properties of the totient function
- For a prime number , all numbers less than Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} are coprime to it, so Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varphi(p) = p -1} .
- For every Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varphi(n) \leq n-1} . This is because there are only Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-1} numbers less than Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} .
- The totient may also be bounded below: for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n>6} it satisfies Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varphi(n) > \sqrt{n}} . \
- A sharper bound is
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varphi(n) > \frac{n}{e^\gamma \log \log n + \frac{3}{\log \log n}}}
- How fast does the totient function grow? For large Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi(n) \approx n} "on average". One way to make this precise is by stating Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{1}{n^2} \sum_{k=1}^n \varphi(k) = \frac{3}{\pi^2} + O \left( \frac{\log n}{n} \right)} , while in contrast Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{1}{n^2} \sum_{k=1}^n k = \frac{1}{2} + O \left( \frac{1}{n} \right).}