2.8 Euler’s Totient Function
For integer \(n>1\), the number of integers less than \(n\) and relatively prime to \(n\) is given by \(\phi (n)\cdot \phi (1)\), with
\(\phi (1) = 1\).
Example 2.8.1. Find all \(a\) such that \((a\, , \, 10) = 1\) with \(\, 1\leq a\leq 10\).
\(\big \{1\, , \, \cancel {2}\, , \, 3\, , \, \cancel {4}\, , \, \cancel {5}\, , \, \cancel {6}\, , \, 7\, ,\, \cancel {8}\, , \, 9\, , \, \cancel {10}\big \} = \big \{1\, , \, 3\, , \, 7\, , \, 9\big \}\)
\(\implies \, \phi (10) = 4 = \) number of element in \((a, 10) = 1\).
This is a group under multiplication mod\(_{10}\)
\(1^{-1} = 1\)
\(3^{-1} = 7\)
\(7^{-1} = 3\)
\(9^{-1} = 9\)
In this group, 9 is the torsion elt.
In general, we denote by; \(\mathbb {Z}^*_n\), the multiplicative group of \(\phi (n)\) elements such that \(a\in \mathbb {Z}_n^*\) if \(a<n\,, \, \, (a,n) = 1\).
Quick check
\(\phi (1) = 1\)
\(\phi (2) = 1\)
\(\phi (3) = \)
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.