Difference between revisions of "Euler's totient function"

From Conservapedia
Jump to navigation Jump to search
(Create previously red link)
 
(cat)
Line 9: Line 9:
 
::<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).
 +
[[Category:Mathematics]]

Revision as of 19:46, October 1, 2011

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

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 \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}} .

Some properties of the totient function

  • For a prime number 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} , 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 <math> \frac{1}{n^2} \sum_{k=1}^n k = \frac{1}{2} + O \left( \frac{1}{n} \right).