Difference between revisions of "Euler's totient function"

From Conservapedia
Jump to navigation Jump to search
(cat)
 
(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 ===
+
== 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).}