Euler's phi function

The first thousand values ​​of the function

The Euler Phi function (different spelling: Euler's φ function , even Euler function called) is a number theoretic function . For every positive natural number , it indicates how many coprime natural numbers there are that are not greater than (also known as the totient of ): ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$

${\displaystyle \varphi (n)\;:=\;{\Big |}\{a\in \mathbb {N} \,|\,1\leq a\leq n\land \operatorname {ggT} (a,n)=1\}{\Big |}}$

Denotes the greatest common factor of and ${\displaystyle \operatorname {ggT} (a,n)}$ ${\displaystyle a}$ ${\displaystyle n.}$

The Phi function is named after Leonhard Euler .

Examples

• As a special case of the empty product (neither prime nor composite number), the number 1 is also coprime to itself, so is ${\displaystyle \varphi (1)=1.}$
• The number 6 is relatively prime to exactly two of the six numbers from 1 to 6 (namely to 1 and 5), so is ${\displaystyle \varphi (6)=2.}$
• The number 13 is prime to each of the twelve numbers from 1 to 12 (but of course not to 13), so is ${\displaystyle \varphi (13)=12.}$

The first 99 values ​​of the phi function are:

${\displaystyle \varphi (n)}$	+0	+1	+2	+3	+4	+5	+6	+7	+8	+9
00+		01	01	02	02	04th	02	06th	04th	06th
10+	04th	10	04th	12	06th	08th	08th	16	06th	18th
20+	08th	12	10	22nd	08th	20th	12	18th	12	28
30+	08th	30th	16	20th	16	24	12	36	18th	24
40+	16	40	12	42	20th	24	22nd	46	16	42
50+	20th	32	24	52	18th	40	24	36	28	58
60+	16	60	30th	36	32	48	20th	66	32	44
70+	24	70	24	72	36	40	36	60	24	78
80+	32	54	40	82	24	64	42	56	40	88
90+	24	72	44	60	46	72	32	96	42	60

properties

Multiplicative function

The Phi function is a multiplicative number theoretic function , so that for coprime numbers and ${\displaystyle m}$ ${\displaystyle n}$

${\displaystyle \varphi (m\cdot n)=\varphi (m)\cdot \varphi (n)}$

applies. An example of this:

${\displaystyle \varphi (18)=\varphi (2)\cdot \varphi (9)=1\cdot 6=6}$

properties

The function assigns the number of units in the remainder class ring to each , i.e. the order of the prime remainder class group . ${\displaystyle \varphi \,}$ ${\displaystyle n\in \mathbb {N} ^{+}}$ ${\displaystyle \varphi (n)\,}$ ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$

Because if there is a unit, there is a with which is equivalent to the existence of an integer with . According to Bézout's lemma , this is equivalent to the coprime numbers of and ${\displaystyle {\overline {a}}\in \mathbb {Z} /n\mathbb {Z} }$ ${\displaystyle {\overline {a}}\in (\mathbb {Z} /n\mathbb {Z} )^{*},}$ ${\displaystyle {\overline {b}}\in \mathbb {Z} /n\mathbb {Z} }$ ${\displaystyle {\overline {a}}\cdot {\overline {b}}={\overline {1}},}$ ${\displaystyle ab\equiv 1\,\mathrm {mod} \,n,}$ ${\displaystyle x}$ ${\displaystyle ab+nx=1\,}$ ${\displaystyle a\,}$ ${\displaystyle n.}$

${\displaystyle \varphi (n)}$is always an even number. ${\displaystyle n>2}$

If the number of elements in the picture is not greater than , then applies ${\displaystyle a_{n}}$ ${\displaystyle \mathrm {im} (\varphi ),}$ ${\displaystyle n}$ ${\displaystyle \lim _{n\to \infty }{\frac {a_{n}}{n}}=0.}$

The image of the Phi function therefore has the natural density 0.

Generating function

The Dirichlet-generating function of the Phi function is related to the Riemann zeta function : ${\displaystyle \zeta }$

${\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)}{n^{s}}}={\frac {\zeta (s-1)}{\zeta (s)}}}$

calculation

Prime numbers

Since a prime number is only divisible by 1 and itself , it is relatively prime to the numbers 1 to . In addition, because it is greater than 1, it is not coprime to itself. It is therefore true ${\displaystyle p}$ ${\displaystyle p-1}$

${\displaystyle \varphi (p)=p-1.}$

Power of prime numbers

A power with a prime number as a base and the exponent has only one prime factor. Therefore, it only has multiples of one in common different from 1. In the range from 1 to these are the numbers ${\displaystyle p^{k}}$ ${\displaystyle p}$ ${\displaystyle k\in \mathbb {N} ^{+}}$ ${\displaystyle p.}$ ${\displaystyle p^{k}}$ ${\displaystyle p}$ ${\displaystyle p^{k}}$

${\displaystyle 1\cdot p,\;2\cdot p,\;3\cdot p,\;\dotsc ,\;p^{k-1}\cdot p=p^{k}}$.

These are numbers that are not too prime . The following therefore applies to Euler's function ${\displaystyle p^{k-1}}$ ${\displaystyle p^{k}}$ ${\displaystyle \varphi }$

${\displaystyle \varphi (p^{k})=p^{k}-p^{k-1}=p^{k-1}(p-1)=p^{k}\left(1-{\frac {1}{p}}\right)}$.

Example:

${\displaystyle \varphi (16)=\varphi (2^{4})=2^{4}-2^{3}=2^{3}\cdot (2-1)=2^{4}\cdot \left(1-{\frac {1}{2}}\right)=8}$.

General calculation formula

The value of Euler's phi function can be determined for each from its canonical prime factorization ${\displaystyle n\in \mathbb {N} ^{+}}$

${\displaystyle n=\prod _{p\mid n}p^{k_{p}}}$

to calculate:

${\displaystyle \varphi (n)=\prod _{p\mid n}p^{k_{p}-1}(p-1)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right)}$,

where the products are formed over all prime numbers that are divisors of . This formula follows directly from the multiplicativity of the Phi function and the formula for prime powers. ${\displaystyle p}$ ${\displaystyle n}$

Example:

${\displaystyle \varphi (72)=\varphi (2^{3}\cdot 3^{2})=2^{3-1}\cdot (2-1)\cdot 3^{2-1}\cdot (3-1)=2^{2}\cdot 1\cdot 3\cdot 2=24}$

or

${\displaystyle \varphi (72)=72\cdot (1-{\tfrac {1}{2}})\cdot (1-{\tfrac {1}{3}})=24}$.

Average order of magnitude

With the Riemann zeta function , the Landau symbol and the following applies: ${\displaystyle \zeta }$ ${\displaystyle {\mathcal {O}}}$ ${\displaystyle \zeta (2)={\tfrac {\pi ^{2}}{6}}}$

${\displaystyle \sum _{n=1}^{N}\varphi (n)={\frac {1}{2\zeta (2)}}N^{2}+{\mathcal {O}}(N\log N)={\frac {3}{\pi ^{2}}}N^{2}+{\mathcal {O}}(N\log N)}$

Because of these two sums are asymptotically equal: ${\displaystyle \sum _{n=1}^{N}{\tfrac {6}{\pi ^{2}}}n={\tfrac {6}{\pi ^{2}}}{\tfrac {N(N+1)}{2}}={\tfrac {3}{\pi ^{2}}}N^{2}+{\mathcal {O}}(N)}$

${\displaystyle \lim _{N\to \infty }{\frac {\sum _{n=1}^{N}\varphi (n)}{\sum _{n=1}^{N}{\frac {6}{\pi ^{2}}}n}}=\lim _{N\to \infty }{\frac {{\frac {3}{\pi ^{2}}}+{\mathcal {O}}\left({\frac {\log N}{N}}\right)}{{\frac {3}{\pi ^{2}}}+{\mathcal {O}}\left({\frac {1}{N}}\right)}}=1}$

One also says:

• The average magnitude of is . ${\displaystyle \varphi (n)}$ ${\displaystyle {\tfrac {6}{\pi ^{2}}}n}$

Fourier transform

Euler's phi function is the discrete Fourier transformation of the GCD , evaluated at point 1:

${\displaystyle {\begin{aligned}{\mathcal {F}}\left\{\mathbf {x} \right\}[m]&=\sum \limits _{k=1}^{n}x_{k}\cdot e^{{-2\pi i}{\frac {mk}{n}}},\quad \mathbf {x_{k}} =\left\{\operatorname {ggT} (k,n)\right\}\quad {\text{für }}\,k\in \left\{1,\dotsc ,n\right\}\\\varphi (n)&={\mathcal {F}}\left\{\mathbf {x} \right\}[1]=\sum \limits _{k=1}^{n}\operatorname {ggT} (k,n)e^{{-2\pi i}{\frac {k}{n}}}\end{aligned}}}$

The real part of this gives the equation

${\displaystyle \varphi (n)=\sum \limits _{k=1}^{n}\operatorname {ggT} (k,n)\cos \left(2\pi {\frac {k}{n}}\right).}$

More relationships

• It even applies to odd ones . ${\displaystyle \varphi (n)>{\frac {\sqrt {n}}{2}}}$ ${\displaystyle n}$ ${\displaystyle \varphi (n)\geq {\sqrt {n}}}$

• The following applies to: ${\displaystyle n\geq 2}$

${\displaystyle \sum _{1\leq j\leq n-1 \atop \operatorname {ggT} (n,j)=1}j={\frac {n}{2}}\varphi (n)}$

• The following applies to all : ${\displaystyle n\in \mathbb {N} ^{+}}$

${\displaystyle \sum _{d>0 \atop d|n}\varphi (d)=n}$

Example: For is the set of positive divisors of by ${\displaystyle n=100}$ ${\displaystyle T(n):=\{t\in \mathbb {N} ^{+}:t|n\}}$ ${\displaystyle n}$

${\displaystyle T(100)=T(2^{2}\cdot 5^{2})=\{2^{m}\cdot 5^{n}:m\in \{0,1,2\},n\in \{0,1,2\}\}=\{1,2,4,5,10,20,25,50,100\}}$

given. Addition of the associated equations ${\displaystyle |T(100)|=(2+1)(2+1)=9}$

${\displaystyle {\begin{aligned}\varphi (1)&=1\\\varphi (2)&=1\\\varphi (4)&=2\\\varphi (5)&=4\\\varphi (10)&=4\\\varphi (20)&=8\\\varphi (25)&=20\\\varphi (50)&=20\\\varphi (100)&=40\end{aligned}}}$

results in:

${\displaystyle {\begin{aligned}\sum _{d>0 \atop d|100}\varphi (d)&=\varphi (1)+\varphi (2)+\varphi (4)+\varphi (5)+\varphi (10)+\varphi (20)+\varphi (25)+\varphi (50)+\varphi (100)\\&=1+1+2+4+4+8+20+20+40=100\end{aligned}}}$

meaning

The phi function finds an important application in the Fermat-Euler theorem :

If two are natural numbers and are prime, is a factor of ${\displaystyle a}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle a^{\varphi (m)}-1:}$

${\displaystyle \operatorname {ggT} (a,m)=1\Rightarrow m\mid a^{\varphi (m)}-1}$

Put a little differently:

${\displaystyle \operatorname {ggT} (a,m)=1\Rightarrow a^{\varphi (m)}\equiv 1{\pmod {m}}}$

A special case (for prime numbers ) of this theorem is the little Fermatsche theorem : ${\displaystyle p}$

${\displaystyle p\nmid a\Rightarrow p\mid a^{p-1}-1}$

${\displaystyle p\nmid a\Rightarrow a^{p-1}\equiv 1{\pmod {p}}}$

The Fermat-Euler theorem is used, among other things, to generate keys for the RSA method in cryptography .

See also

• Highly quoted number
• Highly touted number
• Non-cotient
• Nontotient
• Perfect total number
• Scarce total number

Web links

• Eric W. Weisstein : Totient Function . In: MathWorld (English).
• Sequence of the function values sequence A000010 in OEIS ${\displaystyle \varphi (n)\colon }$
• The first 100,000 values ​​of the Phi function (OEIS)
• Phi calculator
• Florian Luca, Herman te Riele: and : from Euler to Erdös. Nieuw Archief voor Wiskunde, March 2011, PDF. ${\displaystyle \phi }$ ${\displaystyle \sigma }$
• Video: Euler's phi function . Pedagogical University Heidelberg (PHHD) 2012, made available by the Technical Information Library (TIB), doi : 10.5446 / 19894 .

Individual evidence

1. ^ Wolfgang Schramm: The Fourier transform of functions of the greatest common divisor . In: University of West Georgia , Charles University Prague (ed.): Integers Electronic Journal of Combinatorial Number Theory . 8, 2008, p. A50. Retrieved October 24, 2015.
2. ↑ Buchmann: Introduction to Cryptography. Theorem 3.8.4.