A number $a$ is a primitive root mod $n$ if and only if $\{a, a^2 , . . . , a^{\varphi(n)}\}$ is a complete set of residues prime to n.

Question

A number $a$ is a primitive root $\bmod n$ if and only if $\{a, a^2 , . . . , a^{\varphi(n)}\}$ is a complete set of residues prime to $n$. Is this true or false?

Answer 1

True if you define 'a' is primitive root iff order of 'a' is $\phi (n)$.

If this were not true, then for some $i,j \leq \phi (n):$

You would have: $a^i = a^j \implies a^{i-j}=1$ where $i-j < \phi(n)$

This is a contradiction because a is a primitive root and the order is $\phi(n)$ not less than it.

Are you in mat315 at UofT?