Here in the definition of primitive root, it states: "a to be a primitive root modulo n, φ(n) has to be the smallest power of a which is congruent to 1 modulo n" (taking the set of integers)
What my understanding about this statement is that, for any integer $0<a<n$, if it is the primitive root, then, $φ(n)$ has to be the minimum value of $a$ which is congruent to 1 mod n. In particular, there is no mention that the multiplicative order has to be equal to $φ(n)$
But, down here in the examples, it does exactly that, here, contrary to the definition given, the integer $a$ that does have the multiplicative order of $φ(n)$ is accepted as the primitive root.
Where am I misunderstanding the point?
Best Answer
For $a$ relatively prime to $n$ we always have, by Euler's theorem, that $a^{\varphi (n)}\cong1\pmod n$.
Then for $a$ to be a primitive root mod n, $\varphi (n)$ must be the least such value.
That way $a$ generates $C_{\varphi (n)}$.