# 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 from \ equiv 1 \, \ mathrm {mod} \, n,}$${\ displaystyle x}$${\ displaystyle from + 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 \ times p, \; 2 \ times p, \; 3 \ times p, \; \ dotsc, \; p ^ {k-1} \ times 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 {for}} \, 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 .