Algebra Solutions: Compute the Euler totient of all positive integers up to 30

Determine the value $\varphi(n)$ for $1 \leq n \leq 30$ , where $\varphi$ denotes the Euler totient function.

We will use the following facts: $\varphi(p^k) = p^{k-1}(p-1)$ when $p$ is prime and $k \geq 1$ , and if $a$ and $b$ are relatively prime, then $\varphi(ab) = \varphi(a) \varphi(b)$ .

$n$	Reasoning	$\varphi(n)$
1	$\varphi(1) = 1$ .	1
2	$\varphi(2) = 2^0(2-1) = 1$ since 2 is prime.	1
3	$\varphi(3) = 3^0(3-1) = 2$ since 3 is prime.	2
4	$\varphi(4) = \varphi(2^2) = 2^1(2-1) = 2$ .	2
5	$\varphi(5) = 5^0(5-1) = 4$ since 5 is prime.	4
6	$\varphi(6) = \varphi(2 \cdot 3) = \varphi(2) \cdot \varphi(3) = 1 \cdot 2 = 2$ .	2
7	$\varphi(7) = 7^0(7-1) = 6$ since 7 is prime.	6
8	$\varphi(8) = \varphi(2^3) = 2^2(2-1) = 4$ .	4
9	$\varphi(9) = \varphi(3^2) = 3^1(3-1) = 6$ .	6
10	$\varphi(10) = \varphi(2 \cdot 5) = \varphi(2) \cdot \varphi(5) = 1 \cdot 4 = 4$ .	4
11	$\varphi(11) = 11^0(11-1) = 10$ since 11 is prime.	10
12	$\varphi(12) = \varphi(3 \cdot 4) = \varphi(3) \cdot \varphi(4) = 2 \cdot 2 = 4.$	4
13	$\varphi(13) = 13^0(13-1) = 12$ since 13 is prime.	12
14	$\varphi(14) = \varphi(2 \cdot 7) = \varphi(2) \cdot \varphi(7) = 1 \cdot 6 = 6.$	6
15	$\varphi(15) = \varphi(3 \cdot 5) = \varphi(3) \cdot \varphi(5) = 2 \cdot 4 = 8$	8
16	$\varphi(16) = \varphi(2^4) = 2^3(2-1) = 8$ .	8
17	$\varphi(17) = 17^0(17-1) = 16$ since 17 is prime.	16
18	$\varphi(18) = \varphi(2 \cdot 9) = \varphi(2) \cdot \varphi(9) = 1 \cdot 6 = 6$ .	6
19	$\varphi(19) = 19^0(19-1) = 18$ since 19 is prime.	18
20	$\varphi(20) = \varphi(4 \cdot 5) = \varphi(4) \cdot \varphi(5) = 2 \cdot 4 = 8$	8
21	$\varphi(21) = \varphi(3 \cdot 7) = \varphi(3) \cdot \varphi(7) = 2 \cdot 6 = 12$ .	12
22	$\varphi(22) = \varphi(2 \cdot 11) = \varphi(2) \cdot \varphi(11) = 1 \cdot 10 = 10$ .	10
23	$\varphi(23) = 23^0(23-1) = 22$ since 23 is prime.	22
24	$\varphi(24) = \varphi(3 \cdot {8}) =\varphi(3) \cdot \varphi(8) = 2 \cdot 4 = 8$ .	8
25	$\varphi(25) = \varphi(5^2) = 5^1(5-1) = 20$ .	20
26	$\varphi(26) = \varphi(2 \cdot 13) = \varphi(2) \cdot \varphi(13) = 1 \cdot 12 = 12$ .	12
27	$\varphi(27) = \varphi(3^3) = 3^2(3-1) = 18$ .	18
28	$\varphi(28) = \varphi(4 \cdot 7) = \varphi(4) \cdot \varphi(7) = 2 \cdot 6 = 12$	12
29	$\varphi(29) = 29^0(29-1) = 28$ since 29 is prime.	28
30	$\varphi(30) = \varphi(2 \cdot 3 \cdot 5) = \varphi(2) \cdot \varphi(3) \cdot \varphi(5) = 1 \cdot 2 \cdot 4 = 8$	8

Algebra Solutions

Compute the Euler totient of all positive integers up to 30

No comments:

Post a Comment