985: Euler's Totient Function

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

definition of Euler's totient function

---

Topics

About: set

---

The table of contents of this article

• Starting Context
• Target Context
• Orientation
• Main Body
• 1: Structured Description
• 2: Note

---

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:
$\ast \varphi$: $:\mathbb{N}\setminus \{0\}\to \mathbb{N}\setminus \{0\}$
//

Conditions:
$\mathrm{\forall }n\in \mathbb{N}\setminus \{0\}(\varphi (n)=|\{j\in \mathbb{N}\setminus \{0\}|j\le n\wedge gcd(n,j)=1\}|)$
//

---

2: Note

In other words, $\varphi (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, $\varphi (n)$ is the number of the single-element-generators of the n-ordered cyclic group by any $p$, $⟨p⟩$: $⟨p⟩=\{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 $jk=nm$, 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 $⟨p⟩$ is $|\{j\in \mathbb{N}\setminus \{0\}|j\le n\wedge gcd(n,j)=1\}|)=\varphi (n)$.

---

References

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