2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ $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. $\endgroup$ Oct 17, 2018 at 16:58
  • $\begingroup$ @DietrichBurde My comment was in response to an earlier one of yours. I'm now deleting it. $\endgroup$ Oct 17, 2018 at 17:07

4 Answers 4

4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .