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 at 16:58
  • @DietrichBurde My comment was in response to an earlier one of yours. I'm now deleting it. – Ethan Bolker Oct 17 at 17:07
up vote 4 down vote accepted

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.

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 at 17:12

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.