Let \(n\) be a positive integer and \(a\) be an integer relatively prime to \(n\). The order of \(a\) modulo \(n\) is
the smallest positive integer \(k\) for which \(a^{k}\equiv 1\:\left(\mathrm{mod}\: n \right)\). By Euler's theorem,
\(k\leq \phi(n)\). Note that in the multiplicative group \(\mathbb Z_n^*\), the order of \(\overline{a}\) is the order of
\(a\) modulo \(n\).
Example.
For \(a=3\), modulo \(n=8\) we have \(a^1\equiv 3,\; a^2\equiv 1\). Thus \(3\) has order \(2\) modulo \(8\). In
\(\mathbb Z_{8}^*\), the order of \(\overline{3}\) is \(2\). Note that the order is \(2<4=\phi(10)\).
For \(a=3\), modulo \(n=10\) we have \(a^1\equiv 3,\; a^2\equiv 9,\;a^3\equiv 7,\;a^4\equiv 1\).
Thus \(3\) has order \(4\) modulo \(10\). Note that the order is \(4=\phi(10)\).
Proposition.
Let \(k\) be the order of \(a\) modulo \(n\). If \(a^t\equiv 1\:\left(\mathrm{mod}\: n \right)\) for a positive integer \(t\),
then \(k\vert t\). In particular, \(k\vert \phi(n)\).
Proof.
Suppose \(a^t\equiv 1\:\left(\mathrm{mod}\: n \right)\) for a positive integer \(t\). Then obviously \(t\geq k\).
By the Division Theorem \(t=kq+r\), \(0\leq r < k\). Then
\[ a^t=a^{kq+r}=(a^k)^qa^r.\]
Since \(a^t\equiv 1\:\left(\mathrm{mod}\: n \right)\) and \(a^k\equiv 1\:\left(\mathrm{mod}\: n \right)\), we have
\(1\equiv 1\cdot a^r \:\left(\mathrm{mod}\: n \right)\). If \(0< r < k\), \(a^r\equiv 1 \:\left(\mathrm{mod}\: n \right) \)
contradict that \(k\) is the order of \(a\) modulo \(n\). Thus \(r=0\) and consequently \(k\vert t=kq\). Finally,
since \(a^{\phi(n)}\equiv 1\:\left(\mathrm{mod}\: n \right)\), \(k\vert \phi(n)\).
◼
If the order of \(a\) modulo \(n\) is \(\phi(n)\) (i.e., the smallest positive integer \(k\) for which
\(a^{k}\equiv 1\:\left(\mathrm{mod}\: n \right)\) is \(k=\phi(n)\) ), then \(a\) is called a primitive root of \(n\)
or a primitive root modulo \(n\) . Note that in that case \(\{a,a^2,\ldots,a^{\phi(n)}\}\) is a reduced set of
residues modulo \(n\), i.e., \(\mathbb Z_{n}^*=\{\overline{a},\overline{a}^2,\ldots,\overline{a}^{\phi(n)}\}\)
(\(\implies\overline{a}\) is a generator of \(\mathbb Z_{n}^*\) ). (why?)
Example.
\(3\) has order \(4=\phi(10)\) modulo \(10\). So \(3\) is a primitive root of \(10\). Note that \(\overline{3}\) is a
generator of
\[ \mathbb Z_{10}^*=\{\overline{3}^1=\overline{3},\overline{3}^2=\overline{9}, \overline{3}^3=\overline{7}, \overline{3}^4=\overline{1} \}.\]
The positive integers relatively prime to \(n=8\) are \(1,3,5,7\). Their orders modulo \(8\) are \(1,2,2,2\) respectively.
None of them is \(4=\phi(8)\). So \(8\) has no primitive roots. Also \(\mathbb Z_{8}^*\) has no generators.
Proposition.
The number of primitive roots of a positive integer \(n\) is either \(0\) or \(\phi(\phi(n))\).
Proof.
Suppose \(n\) has a primitive root \(a\). Then \(\{a,a^2,\ldots,a^{\phi(n)}\}\) is a reduced set of residues modulo \(n\).
For \(k=1,2,\ldots,\phi(n)\), the order of \(a^k\) is \(\displaystyle\frac{\phi(n)}{\gcd(k,\phi(n))}\) (why?).
Then for \(k=1,2,\ldots,\phi(n)\), \(a^k\) has order \(\phi(n)\) if and only if \(\gcd(k,\phi(n))=1\). Since the number of
positive integers \(k\leq \phi(n)\) is \(\phi(\phi(n))\), the number of primitive roots of \(n\) is \(\phi(\phi(n))\).
◼