Difference between revisions of "Euler totient"

From specialfunctionswiki
Jump to: navigation, search
m (Tom moved page Totient function to Euler phi)
(→‎Videos)
 
(23 intermediate revisions by the same user not shown)
Line 1: Line 1:
−
Euler's totient function (sometimes called Euler's $\phi$ function) is the function <br />
+
__NOTOC__
−
<center>$\phi(n) =$ # of positive integers $\leq n$ that are relatively prime to $n$.</center>
+
Euler's totient function $\phi \colon \{1,2,3,\ldots\} \rightarrow \{1,2,3,\ldots\}$ (not to be confused with the [[Euler phi]]) is defined so that $\phi(n)$ equals the number of positive integers less than or equal to $n$ that are [[relatively prime]] to $n$.  
 +
 
 +
<div align="center">
 +
<gallery>
 +
File:Totientplot,to3500.png|Graph of $\phi$ to $3500$.
 +
</gallery>
 +
</div>
  
 
=Properties=
 
=Properties=
−
<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
 
−
<strong>Theorem:</strong> 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]].
 
−
<div class="mw-collapsible-content">
 
−
<strong>Proof:</strong> █
 
−
</div>
 
−
</div>
 
  
−
<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
+
[[Sum of totient equals zeta(z-1)/zeta(z) for Re(z) greater than 2]]<br />
−
<strong>Theorem:</strong> The function $\phi$ obeys the formula
+
[[Sum of totient equals z/((1-z) squared)]]<br />
−
$$\phi(n) = n \displaystyle\prod_{p | n} \left( 1 - \dfrac{1}{p} \right),$$
+
[[Product representation of totient]]<br />
−
where the notation $p | n$ indicates that $p$ is a prime that divides $n$.  
+
[[Euler totient is multiplicative]]<br />
−
<div class="mw-collapsible-content">
+
 
−
<strong>Proof:</strong> █
+
=Videos=
−
</div>
+
[https://www.youtube.com/watch?v=QbsWEVcjJy0 Euler's Phi Function] (6 October 2010)<br />
−
</div>
+
[https://www.youtube.com/watch?v=ATPiEJIT1FI Euler's Totient Function] (14 October 2011)<br />
 +
[https://www.youtube.com/watch?v=4hu6Z8ZCl5Q Euler Totient Theorem, Fermat Little Theorems] (19 December 2011)<br />
 +
[https://www.youtube.com/watch?v=fjhefD0NrH8 Möbius and Euler totient functions] (2 September 2012)<br />
 +
[https://www.youtube.com/watch?v=IBJuVHGRfLg Prime Factorisation and Euler Totient Function Part 14] (16 April 2014)<br />
 +
[https://www.youtube.com/watch?v=o8NrDpaIfVk Application of Euler Totient Function Part 16] (17 April 2014)<br />
 +
[https://www.youtube.com/watch?v=GZbdmCIhmpA Euler's Totient Function: what it is and how it works] (4 July 2014)<br />
 +
[https://www.youtube.com/watch?v=9Pox0bIgC8g Euler's Totient Theorem: What is Euler's Totient Theorem and Why is it useful?] (6 July 2014)<br />
 +
[https://www.youtube.com/watch?v=F7a6XfxCjbE Euler's Totient Function | How To Find Totient Of A Number Using Euler's Product Formula] (7 July 2014)<br />
 +
[https://www.youtube.com/watch?v=ygfjHZAb0p8 03 Modern cryptography 08 Euler's totient function] (23 September 2014)<br />
 +
[https://www.youtube.com/watch?v=njaJpmBK7QI Euler's totient function] (8 January 2015)<br />
 +
[https://www.youtube.com/watch?v=-NOSYaHh2nE Euler Totient (phi) Function Examples (Part 1)] (27 November 2016)<br />
 +
[https://www.youtube.com/watch?v=EcAT1XmHouk Euler totient function made easy] (17 December 2017)<br />
 +
 
 +
=References=
 +
* {{BookReference|Handbook of mathematical functions|1964|Milton Abramowitz|author2=Irene A. Stegun|prev=findme|next=Sum of totient equals zeta(z-1)/zeta(z) for Re(z) greater than 2}}: $24.3.2 \mathrm{I}.A.$
 +
 
 +
{{:Number theory functions footer}}
  
−
<div class="toccolours mw-collapsible mw-collapsed" style="width:800px">
+
[[Category:SpecialFunction]]
−
<strong>Theorem:</strong> 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 [[e | base of the exponential]] and the notation $d|n$ indicates that $d$ is any [[divisor]] of $n$.
 
−
<div class="mw-collapsible-content">
 
−
<strong>Proof:</strong>  █
 
−
</div>
 
−
</div>
 

Latest revision as of 01:58, 21 December 2017

Euler's totient function $\phi \colon \{1,2,3,\ldots\} \rightarrow \{1,2,3,\ldots\}$ (not to be confused with the Euler phi) is defined so that $\phi(n)$ equals the number of positive integers less than or equal to $n$ that are relatively prime to $n$.

  • Graph of $\phi$ to $3500$.

Properties

Sum of totient equals zeta(z-1)/zeta(z) for Re(z) greater than 2
Sum of totient equals z/((1-z) squared)
Product representation of totient
Euler totient is multiplicative

Videos

Euler's Phi Function (6 October 2010)
Euler's Totient Function (14 October 2011)
Euler Totient Theorem, Fermat Little Theorems (19 December 2011)
Möbius and Euler totient functions (2 September 2012)
Prime Factorisation and Euler Totient Function Part 14 (16 April 2014)
Application of Euler Totient Function Part 16 (17 April 2014)
Euler's Totient Function: what it is and how it works (4 July 2014)
Euler's Totient Theorem: What is Euler's Totient Theorem and Why is it useful? (6 July 2014)
Euler's Totient Function | How To Find Totient Of A Number Using Euler's Product Formula (7 July 2014)
03 Modern cryptography 08 Euler's totient function (23 September 2014)
Euler's totient function (8 January 2015)
Euler Totient (phi) Function Examples (Part 1) (27 November 2016)
Euler totient function made easy (17 December 2017)

References

Number theory functions
Chebthetathumb.png
Chebyshev $\vartheta$
Chebyshevpsithumb.png
Chebyshev $\psi$

Euler $\phi$

Greatest prime factor

Mangoldt
Mertensthumb.png
Mertens

Möbius
Liouvillelambdathumb.png
Liouville $\lambda$

Prime counting
Riemannsiegelzthumb.png
Riemann-Siegel $Z$
Riemannzetathumb.png
Riemann zeta
Divisorsumthumb.png
Sum of divisors

Totient
Retrieved from "http://specialfunctionswiki.org/index.php?title=Euler_totient&oldid=8934"