definition of Euler's totient function
Topics
About: set
The table of contents of this article
Starting Context
- The reader knows a definition of map.
Target Context
- The reader will have a definition of Euler's totient function.
Orientation
There is a list of definitions discussed so far in this site.
There is a list of propositions discussed so far in this site.
Main Body
1: Structured Description
Here is the rules of Structured Description.
Entities:
\(*\phi\): \(: \mathbb{N} \setminus \{0\} \to \mathbb{N} \setminus \{0\}\)
//
Conditions:
\(\forall n \in \mathbb{N} \setminus \{0\} (\phi (n) = \vert \{j \in \mathbb{N} \setminus \{0\} \vert j \le n \land gcd (n, j) = 1\} \vert)\)
//
2: Note
In other words, \(\phi (n)\) is the number of the positive natural numbers equal or smaller than \(n\) that (the positive natural numbers) are relatively prime to \(n\).
In fact, \(\phi (n)\) is the number of the single-element-generators of the n-ordered cyclic group by any \(p\), \(\langle p \rangle\): \(\langle p \rangle = \{p^1, ..., p^n = 1\}\); for a \(p^j\), where \(1 \le j \le n\), to be a generator, for \((p^j)^k = 1\), \(n\) is the smallest such \(k\); while \((p^j)^k = 1\) means that \(j k = n m\), the smallest such \(k\) is \(n / gcd (n, j)\) (because \(k\) does not need \(gcd (n, j)\) as any factor because it is already contained in \(j\), and \(k\) needs the \(n / gcd (n, j)\) factor because \(j\) does not contain it), so, \(n = n / gcd (n, j)\), which means that \(gcd (n, j) = 1\); so, indeed, the number of the single-element-generators of \(\langle p \rangle\) is \(\vert \{j \in \mathbb{N} \setminus \{0\} \vert j \le n \land gcd (n, j) = 1\} \vert) = \phi (n)\).
