986: Positive Natural Number Is Sum of Euler's Totient Function Results of Divisors of Number

<The previous article in this series | The table of contents of this series | The next article in this series>

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
• Target Context
• Orientation
• Main Body
• 1: Structured Description
• 2: Proof
• 3: Note

---

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\}$
$\varphi$: $:\mathbb{N}\setminus \{0\}\to \mathbb{N}\setminus \{0\}$, $=\text{ the Euler's totient function }$
//

Statements:
$n=\sum _{d|n}\varphi (d)$
//

---

2: Proof

Whole Strategy: Step 1: think of the n-ordered cyclic group by any $p$, $⟨p⟩$; Step 2: divide $⟨p⟩$ by the orders of the elements as $\{S_d|d|n\}$, and see that $n=|⟨p⟩|=\sum _{d|n}|S_d|$; Step 3: see that $|S_d|=\varphi (d)$; Step 4: conclude the proposition.

Step 1:

Let us think of the n-ordered cyclic group by any $p$, $⟨p⟩$.

$|⟨p⟩|=n$.

Step 2:

Let us divide $⟨p⟩$ by the orders of the elements as $\{S_d|d|n\}$, where $S_d$ is the subset of $⟨p⟩$ whose elements have the order $d$.

As each element of $⟨p⟩$ has the definite order and the order is a divisor of $n$ by Lagrange's theorem, that is indeed a disjoint division of $⟨p⟩$.

So, $|⟨p⟩|=\sum _{d|n}|S_d|$.

Step 3:

Let us see that $|S_d|=\varphi (d)$.

The fact that $p^j\in S_d$, where $1\le j\le n$, is nothing but that for $kj=nm$, $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=ld$. So, $ld/d=l=gcd(ld,j)$. That means that $j$ is a multiple of $l$ and $gcd(d,j/l)=1$.

As $l\le j\le n=ld$, $1\le j/l\le d$ and $gcd(d,j/l)=1$.

As $|S_d|$ is the count of such $j$ s, it is the count of such $j/l$ s, which is nothing but $\varphi (d)$ by the definition of Euler's totient function.

So, $|S_d|=\varphi (d)$.

Step 4:

So, $n=|⟨p⟩|=\sum _{d|n}|S_d|=\sum _{d|n}\varphi (d)$.

---

3: Note

While the Wikipedia article briefly mentions of the gist of this proof, the article does not explain why $|S_d|$, the number of the $d$-ordered elements in $⟨p⟩$, equals $\varphi (d)$, the number of the single-element-generators of $C_d$: while $|S_d|$ looks to depend on $n$ (at least, at 1st glance), why does it equal $\varphi (d)$, which does not depend on $n$ at all? Our Step 3 has explained that.

In fact, $|S_d|=\varphi (d)$ holds because we are talking about a cyclic $⟨p⟩$; for a general group, $G$, $|S_d|=\varphi (d)$ does not necessarily hold.

---

References

<The previous article in this series | The table of contents of this series | The next article in this series>