# 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?

• $3$ is a generator of the cyclic group $U(7)$, the group of units of the ring $\Bbb{Z}/7\Bbb{Z}$. Have a look at this site for this, it has been answered here, for $U(p)$ and more generally. For a duplicate with $p=31$, see here. – Dietrich Burde Oct 17 '18 at 16:58
• @DietrichBurde My comment was in response to an earlier one of yours. I'm now deleting it. – Ethan Bolker Oct 17 '18 at 17:07

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

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\!:\,\ \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.

• @Downvoter If something is not clear then please feel welcome to ask questions and I will happily elaborate. – Bill Dubuque Oct 17 '18 at 17:12