description/proof of that positive natural number is sum of Euler's totient function results of divisors of number
Topics
About: set
The table of contents of this article
Starting Context
- The reader knows a definition of Euler's totient function.
- The reader knows a definition of order of element of group.
- The reader admits Lagrange's theorem.
Target Context
- The reader will have a description and a proof of the proposition that any positive natural number is the sum of the Euler's totient function results of the divisors of the number.
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:
\(n\): \(\in \mathbb{N} \setminus \{0\}\)
\(\phi\): \(: \mathbb{N} \setminus \{0\} \to \mathbb{N} \setminus \{0\}\), \(= \text{ the Euler's totient function }\)
//
Statements:
\(n = \sum_{d \vert n} \phi (d)\)
//
2: Proof
Whole Strategy: Step 1: think of the n-ordered cyclic group by any \(p\), \(\langle p \rangle\); Step 2: divide \(\langle p \rangle\) by the orders of the elements as \(\{S_d \vert d \vert n\}\), and see that \(n = \vert \langle p \rangle \vert = \sum_{d \vert n} \vert S_d \vert\); Step 3: see that \(\vert S_d \vert = \phi (d)\); Step 4: conclude the proposition.
Step 1:
Let us think of the n-ordered cyclic group by any \(p\), \(\langle p \rangle\).
\(\vert \langle p \rangle \vert = n\).
Step 2:
Let us divide \(\langle p \rangle\) by the orders of the elements as \(\{S_d \vert d \vert n\}\), where \(S_d\) is the subset of \(\langle p \rangle\) whose elements have the order \(d\).
As each element of \(\langle p \rangle\) has the definite order and the order is a divisor of \(n\) by Lagrange's theorem, that is indeed a disjoint division of \(\langle p \rangle\).
So, \(\vert \langle p \rangle \vert = \sum_{d \vert n} \vert S_d \vert\).
Step 3:
Let us see that \(\vert S_d \vert = \phi (d)\).
The fact that \(p^j \in S_d\), where \(1 \le j \le n\), is nothing but that for \(k j = n m\), \(d\) is the smallest such \(k\).
But 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, \(d = n / gcd (n, j)\), which means that \(n / d = gcd (n, j)\). As \(d\) is a divisor of \(n\), let \(n = l d\). So, \(l d / d = l = gcd (l d, j)\). That means that \(j\) is a multiple of \(l\) and \(gcd (d, j / l) = 1\).
As \(l \le j \le n = l d\), \(1 \le j / l \le d\) and \(gcd (d, j / l) = 1\).
As \(\vert S_d \vert\) is the count of such \(j\) s, it is the count of such \(j / l\) s, which is nothing but \(\phi (d)\) by the definition of Euler's totient function.
So, \(\vert S_d \vert = \phi (d)\).
Step 4:
So, \(n = \vert \langle p \rangle \vert = \sum_{d \vert n} \vert S_d \vert = \sum_{d \vert n} \phi (d)\).
3: Note
While the Wikipedia article briefly mentions of the gist of this proof, the article does not explain why \(\vert S_d \vert\), the number of the \(d\)-ordered elements in \(\langle p \rangle\), equals \(\phi (d)\), the number of the single-element-generators of \(C_d\): while \(\vert S_d \vert\) looks to depend on \(n\) (at least, at 1st glance), why does it equal \(\phi (d)\), which does not depend on \(n\) at all? Our Step 3 has explained that.
In fact, \(\vert S_d \vert = \phi (d)\) holds because we are talking about a cyclic \(\langle p \rangle\); for a general group, \(G\), \(\vert S_d \vert = \phi (d)\) does not necessarily hold.
