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 ):
![n](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
![n](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
![n](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
![{\ displaystyle \ varphi (n) \;: = \; {\ Big |} \ {a \ in \ mathbb {N} \, | \, 1 \ leq a \ leq n \ land \ operatorname {ggT} (a , n) = 1 \} {\ Big |}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/820557db0a686b69c15cc51dbd5f4ebdd66886cf)
Denotes the greatest common factor of and![\ operatorname {ggT} (a, n)](https://wikimedia.org/api/rest_v1/media/math/render/svg/16890db93b6e7d5725ca22803f85f519258c39e7)
![a](https://wikimedia.org/api/rest_v1/media/math/render/svg/ffd2487510aa438433a2579450ab2b3d557e5edc)
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
- The number 6 is relatively prime to exactly two of the six numbers from 1 to 6 (namely to 1 and 5), so is
- The number 13 is prime to each of the twelve numbers from 1 to 12 (but of course not to 13), so is
The first 99 values of the phi function are:
|
+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![m](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a07d98bb302f3856cbabc47b2b9016692e3f7bc)
![\ varphi (m \ cdot n) = \ varphi (m) \ cdot \ varphi (n)](https://wikimedia.org/api/rest_v1/media/math/render/svg/b66ca287034aade183eb0b51293fc5cdc594f1bd)
applies. An example of this:
![{\ displaystyle \ varphi (18) = \ varphi (2) \ cdot \ varphi (9) = 1 \ cdot 6 = 6}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5d4cb8c49b2e039a8d7165b0010e00a76c1c8739)
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 .
![\ varphi \,](https://wikimedia.org/api/rest_v1/media/math/render/svg/48fea757a76cc11e5f8aaf6933416ff0df27ba2a)
![n \ in \ mathbb {N} ^ {+}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3153bd419225b1dd1067de6dc35ef104c83aab2b)
![\ mathbb {Z} / n \ mathbb {Z}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f2120ebbc85f91df66c6de5446367bf9fd620844)
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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f264f533a2f370df95fe6f3a03dcab0c397834d6)
![{\ displaystyle {\ overline {a}} \ in (\ mathbb {Z} / n \ mathbb {Z}) ^ {*},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fe80bcab3551162ef443a379f5d5e475b39e63a1)
![{\ displaystyle {\ overline {b}} \ in \ mathbb {Z} / n \ mathbb {Z}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/49af2fa4a53083cb840299ee93c47558b687e3e4)
![\ overline {a} \ cdot \ overline {b} = \ overline {1},](https://wikimedia.org/api/rest_v1/media/math/render/svg/2c6075ce9b4be7a56222e17e693438f38a685203)
![from \ equiv 1 \, {\ mathrm {mod}} \, n,](https://wikimedia.org/api/rest_v1/media/math/render/svg/76dfa599b9530d9877bb8b5810e59b3f08773d90)
![x](https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4)
![from + nx = 1 \,](https://wikimedia.org/api/rest_v1/media/math/render/svg/d2ecbcd650a0d071fe81e336a6c87134bab4a319)
![a \,](https://wikimedia.org/api/rest_v1/media/math/render/svg/1d73aa5354c24942dab5316be466465a9d171510)
is always an even number.
![n> 2](https://wikimedia.org/api/rest_v1/media/math/render/svg/44e71ac55b9fbf1e9f341b946cda63d61d3ef2cd)
If the number of elements in the picture is not greater than , then applies
![{\ mathrm {im}} (\ varphi),](https://wikimedia.org/api/rest_v1/media/math/render/svg/ff4232050c0cbe3f162c2a160a72f9677733a214)
![n](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
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 :
![\ zeta](https://wikimedia.org/api/rest_v1/media/math/render/svg/d5c3916703cae7938143d38865f78f27faadd4ae)
![\ sum _ {{n = 1}} ^ {\ infty} {\ frac {\ varphi (n)} {n ^ {s}}} = {\ frac {\ zeta (s-1)} {\ zeta ( s)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/503a149acd9f861d3db81875ce98fcb458afbf9e)
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
![p](https://wikimedia.org/api/rest_v1/media/math/render/svg/81eac1e205430d1f40810df36a0edffdc367af36)
![p-1](https://wikimedia.org/api/rest_v1/media/math/render/svg/f356ae51988add41a7da343e6b6d48fa968da162)
![\ varphi (p) = p-1.](https://wikimedia.org/api/rest_v1/media/math/render/svg/6fae42b5384db7618dd87cbe7df21169462f4f10)
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
![p ^ {k}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e017c102135ab13bdf501dc1c1b5fd1840a97822)
![p](https://wikimedia.org/api/rest_v1/media/math/render/svg/81eac1e205430d1f40810df36a0edffdc367af36)
![k \ in \ mathbb {N} ^ {+}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6c8abd3366b703d9dc620115174fe692aeb5ded4)
![p.](https://wikimedia.org/api/rest_v1/media/math/render/svg/88532f4eab1d4cef71ef96c0f8c98cac36fd9257)
![p ^ {k}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e017c102135ab13bdf501dc1c1b5fd1840a97822)
![p](https://wikimedia.org/api/rest_v1/media/math/render/svg/81eac1e205430d1f40810df36a0edffdc367af36)
![p ^ {k}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e017c102135ab13bdf501dc1c1b5fd1840a97822)
-
.
These are numbers that are not too prime . The following therefore applies to Euler's function
![p ^ {{k-1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/db593d7e6059ffe29c98cc5da26b7174292b9830)
![p ^ {k}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e017c102135ab13bdf501dc1c1b5fd1840a97822)
![\ varphi](https://wikimedia.org/api/rest_v1/media/math/render/svg/33ee699558d09cf9d653f6351f9fda0b2f4aaa3e)
-
.
Example:
-
.
General calculation formula
The value of Euler's phi function can be determined for each from its canonical prime factorization
![n = \ prod _ {{p \ mid n}} p ^ {{k_ {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dd6aa631f81f130b9c8bdd9c289becc01db7e549)
to calculate:
-
,
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.
![p](https://wikimedia.org/api/rest_v1/media/math/render/svg/81eac1e205430d1f40810df36a0edffdc367af36)
![n](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
Example:
![\ varphi (72) = \ varphi (2 ^ {3} \ times 3 ^ {2}) = 2 ^ {{3-1}} \ times (2-1) \ times 3 ^ {{2-1}} \ cdot (3-1) = 2 ^ {2} \ times 1 \ times 3 \ times 2 = 24](https://wikimedia.org/api/rest_v1/media/math/render/svg/464d656a054f9907f6ce843c9f786315cfd71503)
or
-
.
Average order of magnitude
With the Riemann zeta function , the Landau symbol and the following applies:
![{\ mathcal {O}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d6ae2ed4058fb748a183d9ada8aea50a00d0c89f)
![{\ displaystyle \ zeta (2) = {\ tfrac {\ pi ^ {2}} {6}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/45d1ec452874d8b1f31260d42ccd6c91eaa24b98)
![{\ 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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/235513f21957cb909455ae1b504404117b0d7a76)
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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bfab00533675762c5a6b5126085b571407696cbc)
![{\ 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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8ad123bab6d91e2abaa5478279ba07368d64e13c)
One also says:
- The average magnitude of is .
![\ varphi (n)](https://wikimedia.org/api/rest_v1/media/math/render/svg/f067864064667dd5f8b2508b9cbf983d89788629)
![{\ displaystyle {\ tfrac {6} {\ pi ^ {2}}} n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4c58e931e46d6e60fdec37564d85727babb0ee00)
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2772e5638dc7bbaa5a391e21634526953583a799)
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).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/32621862028c948af06b4ca1373bf4d4453e316f)
More relationships
- It even applies to odd ones .
![{\ displaystyle \ varphi (n)> {\ frac {\ sqrt {n}} {2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f590801f444050cc94a2d4ac29a8b96b5a5f9e84)
![n](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
![{\ displaystyle \ varphi (n) \ geq {\ sqrt {n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cedbc900df455541c7f6d8cf816415bc91f95679)
- The following applies to:
![n \ geq 2](https://wikimedia.org/api/rest_v1/media/math/render/svg/e6bf67f9d06ca3af619657f8d20ee1322da77174)
![{\ displaystyle \ sum _ {1 \ leq j \ leq n-1 \ atop \ operatorname {ggT} (n, j) = 1} j = {\ frac {n} {2}} \ varphi (n)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/58a9b029d7d6028392e98346affec0a46f316800)
- The following applies to all :
![n \ in \ mathbb {N} ^ {+}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3153bd419225b1dd1067de6dc35ef104c83aab2b)
![\ sum_ {d> 0 \ atop d | n} \ varphi (d) = n](https://wikimedia.org/api/rest_v1/media/math/render/svg/090a490071e8dede02c935e5678df67b7c62f98a)
-
Example: For is the set of positive divisors of by
![n = 100](https://wikimedia.org/api/rest_v1/media/math/render/svg/71cd41fc765ed6d699aa54d45e56247e80122645)
![{\ displaystyle T (n): = \ {t \ in \ mathbb {N} ^ {+}: t | n \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5cad4642b45271d74e68db6a953a5ddc003c596d)
![n](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
![T (100) = T (2 ^ 2 \ times 5 ^ 2) = \ {2 ^ m \ times 5 ^ n: m \ in \ {0,1,2 \}, n \ in \ {0,1, 2 \} \} = \ {1,2,4,5,10,20,25,50,100 \}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2bfb950e62fd785296243141ef3041d1d035e4f8)
- given. Addition of the associated equations
![| T (100) | = (2 + 1) (2 + 1) = 9](https://wikimedia.org/api/rest_v1/media/math/render/svg/d962428dea8ff3e0326e41431533d2533ec4ca48)
![\ begin {align} \ 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 {align}](https://wikimedia.org/api/rest_v1/media/math/render/svg/35bfa7cd499a3c0aa74398a959c96fa0df41c86e)
- 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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c792eec0f832ac55c492e8d7aba44a894d3c1b53)
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![a](https://wikimedia.org/api/rest_v1/media/math/render/svg/ffd2487510aa438433a2579450ab2b3d557e5edc)
![m](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a07d98bb302f3856cbabc47b2b9016692e3f7bc)
![m](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a07d98bb302f3856cbabc47b2b9016692e3f7bc)
![\ operatorname {ggT} (a, m) = 1 \ Rightarrow m \ mid a ^ {{\ varphi (m)}} - 1](https://wikimedia.org/api/rest_v1/media/math/render/svg/1c2f55e9988560616f0f45ffced48619e7e149e6)
Put a little differently:
![\ operatorname {ggT} (a, m) = 1 \ Rightarrow a ^ {{\ varphi (m)}} \ equiv 1 {\ pmod m}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a904394ce8d609496df707d1b7642716c06f5983)
A special case (for prime numbers ) of this theorem is the little Fermatsche theorem :
![p](https://wikimedia.org/api/rest_v1/media/math/render/svg/81eac1e205430d1f40810df36a0edffdc367af36)
![p \ nmid a \ Rightarrow p \ mid a ^ {{p-1}} - 1](https://wikimedia.org/api/rest_v1/media/math/render/svg/ec541cc07fcf80bd4893193b12fb6db2bc86847b)
![p \ nmid a \ Rightarrow a ^ {{p-1}} \ equiv 1 {\ pmod p}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e01ca51278f401375e0a70cc565a9e0e2be7dc39)
The Fermat-Euler theorem is used, among other things, to generate keys for the RSA method in cryptography .
See also
Web links
Individual evidence
-
^ 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.
-
↑ Buchmann: Introduction to Cryptography. Theorem 3.8.4.