Exhibit a reduced residue system mod 7 composed entirely of powers of 3 By trial, I configured that $3,3^2,3^3,3^4,3^5,3^6$ is a reduced residue system composed entirely of powers of $3$. However, why this is happening? Is it true for all relatively prime numbers, though?
 A: No, it is not true for all relatively prime numbers. For example try powers of $2$ and you will find out it is not a reduced residue system. Now why is that happening? If $\gcd(a,n)=1$ then by Euler's theorem $a^{\phi(n)}\equiv 1$(mod $n$). Now, if $\phi(n)$ is also the smallest natural number $m$ for which $a^m\equiv 1$(mod $n$) then $a$ is called a primitive root mod $n$. In that case all invertible elements mod $n$ are powers of $a$. It follows from the fact that if you look at the set $\{1,a,a^2,...,a^{\phi(n)-1}\}$ then it contains $\phi(n)$ different elements. Let's prove that. Suppose $a^i\equiv a^j$(mod $n$) for $0\leq i<j\leq\phi(n)-1$. Then by multiplying both sides by $a^{-i}$ we get $a^{j-i}\equiv 1$(mod $n$) when $1\leq j-i<\phi(n)$ which contradicts the fact that $a$ is a primitive root. So that is what happening in your case-$3$ is a primitive root mod $7$. By the way, not every natural number $n$ has primitive roots, but every prime number does. And if $n$ has a primitive root then there are actually $\phi(\phi(n))$ of them. 
A: Trial was the right way to go.
This is happening because $3$ is a primitive root for $7$: a number whose powers fill out the reduced residue system.
Every prime modulus has primitive roots. There is no easy way to find them. $2$ is not one for $7$ as you can tell by looking at the sequence of its powers, modulo $7$. They repeat with period $3$, not $6$.
A: Yes, that works with the number $3$. However, it doesn't work if you use $2$ instead of $3$, because any power of $2$ is congruent to $1$, $2$, or $4$ modulo $7$. And if you were working with $13$ instead of $7$, $3$ wouldn't work either, because every power of $3$ is congruent to $1$, $3$, or $9$ modulo $13$. You must check it case by case.
A: Hint $\bmod 7\!:\,\  \overbrace{3^{\large 6}\equiv 1}^{\large \mu\rm Fermat},\ 3^{\large 2},3^{\large 3}\not\equiv 1\,\Rightarrow\, 3\,$ has order $\,6,\,$ by below

Order Test $\,\ \,a\,$ has order $\,n\iff a^{ n} = 1\,$ but $\,a^{n/p} \not= 1\,$ for every prime $\,p\mid n.\,$ 
Proof $\ (\Leftarrow)\ $ If $\,a\,$ has $\,\rm\color{#c00}{order\ k}\,$ then $\,k\mid n.\,$  If $\,k < n\,$ then $\,k\,$ is proper divisor of $\,n\,$ therefore $\,k\,$ must omit at least one prime $\,p\,$ from the unique prime factorization of $\,n,\,$ hence 
$\,k\mid n/p,\,$ say $\, kj = n/p,\,$ so $\,a^{n/p} = (\color{#c00}{a^k})^j= \color{#c00}1^j= 1,\,$ contra hypothesis. $\ (\Rightarrow)\ $ By definition of order.
Remark $ $ It is a classical result that the group of units (invertibles) of $\,\Bbb Z/n\,$ is cyclic $\iff n = 1,2,4, p^k\,$ or $\,2p^k,\,$ for $p$ an odd prime. 
