Eulers Totient Function
- Tags
- math
Is a function that counts that number of positive integers less than a given integer \( n \) that are coprime to \( n \). \[ \Phi (n) = |\{ m \in \mathbb{N} : 1 \leq m < n \land \gcd (m) = 1 \}| \]
In the special case that \( n \) is prime, \( \Phi(n) = n-1 \), because \( n \) has no factors other than 1 and itself.
\begin{figure}
\centering
\begin{tikzpicture}
\begin{axis}[ybar, bar width=0.5, width=\textwidth]
\addplot+ coordinates {(1,1) (2,1) (3,2) (4,2) (5,4) (6,2) (7,6) (8,4) (9,6) (10,4) (11,10) (12,4) (13,12) (14,6) (15,8) (16,8) (17,16) (18,6) (19,18) (20,8) (21,12) (22,10) (23,22) (24,8) (25,20) (26,12) (27,18) (28,12) (29,28) (30,8) (31,30) (32,16) (33,20) (34,16) (35,24) (36,12) (37,36) (38,18) (39,24) (40,16) (41,40) (42,12) (43,42) (44,20) (45,24) (46,22) (47,46) (48,16) (49,42) (50,20) (51,32) (52,24) (53,52) (54,18) (55,40) (56,24) (57,36) (58,28) (59,58) (60,16) (61,60) (62,30) (63,36) (64,32) (65,48) (66,20) (67,66) (68,32) (69,44) (70,24) (71,70) (72,24) (73,72) (74,36) (75,40) (76,36) (77,60) (78,24) (79,78) (80,32) (81,54) (82,40) (83,82) (84,24) (85,64) (86,42) (87,56) (88,40) (89,88) (90,24) (91,72) (92,44) (93,60) (94,46) (95,72) (96,32) (97,96) (98,42) (99,60) (100,40) };
\end{axis}
\end{tikzpicture}
\caption{List of the first couple totient function outputs. \label{fig:totient}}
\end{figure}Observe in fig:totient that the values of the quotient function spikes at prime numbers and doesn't come as close for other values. This is due to the special case described above where primes are coprime with all numbers below them. As we raise the numbers the frequency of primes encountered decreases leading to very infrequent spikes.
Formula
The formula for the quotient of the number \( n \) with prime factorisation \( p_1 \times p_2 \times p_3 \times \dots \times p_k \) is:
\begin{align}
\Phi(n) = n (1 - \frac{1}{p_1}) (1 - \frac{1}{p_2}) \dots (1 - \frac{1}{p_k})
\end{align}Multiplicative Property
\begin{align}
\Phi(ab) = \Phi(a) \Phi(b) \; \text{if} \gcd(a,b) = 1
\end{align}