Euler totient function: Difference between revisions

Latest revision as of 11:01, 24 October 2023

This article is about a basic definition in group theory. The article text may, however, contain advanced material.
VIEW: Definitions built on this | Facts about this: (facts closely related to Euler totient function, all facts related to Euler totient function) |Survey articles about this | Survey articles about definitions built on this
VIEW RELATED: Analogues of this | Variations of this | Opposites of this |[SHOW MORE]

View a complete list of basic definitions in group theory | Go through a guided tour for beginners to this wiki

Definitions

The Euler totient function, also known as the Euler-phi function, on a natural number $n$ , denoted $φ (n)$ , is defined in the following equivalent ways:

as the number of positive integers not greater than $n$ that are coprime to $n$ .
as the number of generators of the cyclic group of order $n$ .

Facts

Every natural number is the sum of the Euler totient function on positive divisors

For any natural number $n$ , we have $n = \sum_{d | n} φ (n)$ , where the summation runs over all positive divisors of $n$ .

Evaluation on prime powers

For any prime $p$ and positive integer $k$ , the value of Euler totient function on $p^{k}$ is given by the formula $φ (p^{k}) = p^{k - 1} (p - 1)$ . This is an immediate application of the previous fact.

Multiplicative function

The Euler totient function is multiplicative, that is, if $m$ and $n$ are coprime, then $φ (m n) = φ (m) φ (n)$ . For full proof, see Euler totient function is multiplicative.

Explicit formula

Knowing the prime factorization of $n$ , we can evaluate $φ (n)$ by repeated applications of the above facts.
However, knowing only the distinct prime factors of the number is sufficient, because the value of Euler totient function on it is then given by the formula $φ (n) = n \prod_{p} (1 - \frac{1}{p})$ , where here the product is evaluated over all distinct prime factors of $n$ .

@@ Line 12: / Line 12: @@
 For any natural number <math>n</math>, we have <math>n=\sum_{d|n}\varphi(n)</math>, where the summation runs over all positive divisors of <math>n</math>.
-<br/>
 ===Evaluation on prime powers===
 For any prime <math>p</math> and positive integer <math>k</math>, the value of Euler totient function on <math>p^{k}</math> is given by the formula <math>\varphi(p^{k})=p^{k-1}(p-1)</math>. This is an immediate application of the previous fact.
-<br/>
+===Multiplicative function===
-===Multiplicative if coprime===
+The Euler totient function is multiplicative, that is, if <math>m</math> and <math>n</math> are coprime, then <math>\varphi(mn)=\varphi(m)\varphi(n)</math>.
-The Euler-phi function is multiplicative on coprime numbers, that is, if <math>m</math> and <math>n</math> are coprime, then <math>\varphi(mn)=\varphi(m)\varphi(n)</math>.
+For full proof, see [[Euler totient function is multiplicative]].
-For full proof, see [[Euler-phi function is multiplicative if coprime]].
-<br/>
 ==Explicit formula==
 Knowing the prime factorization of <math>n</math>, we can evaluate <math>\varphi(n)</math> by repeated applications of the above facts.
 <br/>However, knowing only the distinct prime factors of the number is sufficient, because the value of Euler totient function on it is then given by the formula <math>\varphi(n)=n\prod_{p}(1-\frac1{p})</math>, where here the product is evaluated over all distinct prime factors of <math>n</math>.
+==See also==
+[[Group of units modulo n]], a natural group to consider of order <math>\varphi(n)</math>.