mjhjmtu

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?

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^mequiv 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^iequiv a^j$(mod $n$) for $0leq i<jleqphi(n)-1$. Then by multiplying both sides by $a^-i$ we get $a^j-iequiv 1$(mod $n$) when $1leq 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.

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$.

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.

Hint $bmod 7!:, overbrace3^large 6equiv 1^large murm Fermat, 3^large 2,3^large 3notequiv 1,Rightarrow, 3,$ has order $,6,,$ by below

Order Test $, ,a,$ has order $,niff a^ n = 1,$ but $,a^n/p not= 1,$ for every prime $,pmid n.,$

Proof $ (Leftarrow) $ If $,a,$ has $,rmcolor#c00order k,$ then $,kmid 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
$,kmid n/p,,$ say $, kj = n/p,,$ so $,a^n/p = (color#c00a^k)^j= color#c001^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.