$$\\\mathbf{How\ to\ calcultate\ the\ \textit{Euler phi function} \ \phi(n):}\\
$ We have the prime factorization of n = p_1\cdot p_2\cdot p_3 \cdots\\
\phi(n) = n \cdot (1-\frac{1}{p_1})\cdot (1-\frac{1}{p_2}) \cdot (1-\frac{1}{p_3}) \cdots$$
$$\\\mathbf{Example\ 1: n = 6 } $\\
The prime factorization of 6 = 2 * 3 = p_1*p_2 \\
\phi(6) = 6 \cdot (1-\frac{1}{2}) \cdot (1-\frac{1}{3}) \\
\phi(6) = 6 \cdot \frac{1}{2} \cdot \frac{2}{3} \\
\phi(6) = \frac{6}{3} \\
\phi(6) = 2$$
$$\\\mathbf{Example\ 2: n = 9 } $\\
The prime factorization of 9 = 3^2 = p_1^2 \\
\phi(9) = 9 \cdot (1-\frac{1}{3}) \\
\phi(9) = 9 \cdot \frac{2}{3} \\
\phi(6) = 3 \cdot 2 \\
\phi(6) = 6$$
$$\\\mathbf{Example\ 3: n = 7 } $\\
The prime factorization of 7 = 7 = p_1 \qquad 7 $ is a prime number!$ \\
\phi(7) = 7 \cdot (1-\frac{1}{7}) \\
\phi(7) = 7 \cdot \frac{6}{7} \\
\phi(7) = 6$$
$$\\\mathbf{Example\ 4: n = 11 } $\\
The prime factorization of 11 = 11 = p_1 \qquad 11 $ is a prime number!$ \\
\phi(11) = 11 \cdot (1-\frac{1}{11}) \\
\phi(11) = 11 \cdot \frac{10}{11} \\
\phi(11) = 10$$
$$\boxed{\text{ In general $ \phi(p) = p-1 $, if p is a prime number }}\\\\
\begin{array}{lr}
p = 2: &\phi(2) = 1 \qquad =(2-1)\\
p = 3: &\phi(3) = 2 \qquad =(3-1)\\
p = 5: &\phi(5) = 4 \qquad =(5-1)\\
p = 7: &\phi(7) = 6 \qquad =(7-1)\\
p = 11: &\phi(11) = 10 \qquad =(11-1)\\
p = 13: &\phi(13) = 12 \qquad =(13-1)\\
\cdots & \phi(p) = p-1
\end{array}$$
The first 99 values of the Phi function are:
+0 | +1 | +2 | +3 | +4 | +5 | +6 | +7 | +8 | +9 | |
---|---|---|---|---|---|---|---|---|---|---|
0+ | 1 | 1 | 2 | 2 | 4 | 2 | 6 | 4 | 6 | |
10+ | 4 | 10 | 4 | 12 | 6 | 8 | 8 | 16 | 6 | 18 |
20+ | 8 | 12 | 10 | 22 | 8 | 20 | 12 | 18 | 12 | 28 |
30+ | 8 | 30 | 16 | 20 | 16 | 24 | 12 | 36 | 18 | 24 |
40+ | 16 | 40 | 12 | 42 | 20 | 24 | 22 | 46 | 16 | 42 |
50+ | 20 | 32 | 24 | 52 | 18 | 40 | 24 | 36 | 28 | 58 |
60+ | 16 | 60 | 30 | 36 | 32 | 48 | 20 | 66 | 32 | 44 |
70+ | 24 | 70 | 24 | 72 | 36 | 40 | 36 | 60 | 24 | 78 |
80+ | 32 | 54 | 40 | 82 | 24 | 64 | 42 | 56 | 40 | 88 |
90+ | 24 | 72 | 44 | 60 | 46 | 72 | 32 | 96 | 42 | 60 |