Euler totient function

The Euler totient function $𝜙 : ℕ \to ℕ$ is defined such that $𝜙 (1) = 1$ and $𝜙 (𝑛)$ is the number of positive integers less than or equal to $𝑛$ relatively prime with $𝑛$ ¹, called the totient #m/def/num

$𝑛$	1	2	3	4	5	6	7	8	9	10	11	12
coprimes	1	1	1,2	1,3	1,2,3,4	1,5	1,2,3,4,5,6	1,3,5,7	1,2,4,5,7,8	1,3,7,9	1,2,3,4,5,6,7,8,9,10	1,5,7,11
$𝜙 (𝑛)$	1	1	2	2	4	2	6	4	6	4	10	4

Properties

For any prime $𝑝$ , $𝜙 (𝑝 𝑛) = 𝑝 𝑛 - 𝑝 𝑛 - 1$ .

Proof of 1.

Consider the set $ℕ 𝑝 𝑛$ of size $𝑝 𝑛$ . The only elements which are not relatively prime to $𝑝 𝑛$ are those which are divisible by $𝑝$ , of which there are $𝑝 𝑛 𝑝 = 𝑝 𝑛 - 1$ , proving ^P1.

#state/tidy | #lang/en | #SemBr

2017, Contemporary Abstract Algebra, p. 83 ↩

Euler totient function

Properties

Footnotes