Show that $\operatorname{ord}((2 \bmod 61)^n)=60 \iff\gcd(60,n)=1$

Question

I have an old exam with this question:

Given $(\mathbb{Z}/61\mathbb{Z})^{*}$ show that for $n \in \mathbb{N}$ we have:

$$\operatorname{ord}((2 \bmod 61)^n)=60\iff\gcd(60,n)=1.$$

Update:

I have something: $(2^n \bmod 61)^{60}=2^{60n} \bmod 61 = 2^{60} \bmod 61 = 1 \bmod 61 .$ I conclude from this: $60n=60$, and this holds for $n=1$, so $\gcd(60,n)=1$. I find this quite ugly to be honest.

Answer 1

The way I look at it is this:

If $a = [2] \in (\Bbb Z_{61})^{\times}$ then the order of $[2]$ is clearly greater than $5$. A few simple calculations show:

$[2]^6 = [3]$; $[2]^{10} = ([2]^4)([2]^6) = [48]$; $[2]^{12} = ([2]^6)^2 = [9]$,

$[2]^{15} = ([2]^{12})([2]^3) = [9][8] = [11]$; $[2]^{20} = ([2]^6)^3([2]^2) = [27][4] = [47]$,

$[2]^{30} = ([2]^{15})^2 = [11]^2 = [60]$, which show that $[2]$ is thus a generator for the cyclic group $(\Bbb Z_{61})^{\times}$.

Now for a cyclic group of order $m$ with generator $a$ we have for $n \in \Bbb N$:

$|a^n| = \dfrac{m}{\text{gcd}(m,n)}$, so if we set $m = 60$, you have the desired result.

(There is nothing special about $61$ in this, but in general, we DO require a generator of $(\Bbb Z_p)^{\times}$ if $p$ is an arbitrary prime).

Answer 2

All nonzero element $a \in \mathbb F_{61}$ can be represent by $2^n$ for some $n$ because $2$ is a primitive root of $61$ so $a=2^n$ for some $n$. On the other hand, if the order of an element $a\in \mathbb F_{61}$ is equal to $60$, then $a$ is a primitive root of $61$ i.e. a generator of the cyclic group $\mathbb F_{61}^*$.

There are sixteen primitive roots of $61$ which are known to be the following:$$\{2,6,7,10,17,18,26,30,31,35,43,44,51,54,55,59\}$$ A way to prove the statement is therefore represent each of these $16$ elements as a power of (the primitive root) $2$ and verify that $60$ and the corresponding exponents of $2$ are coprimes. This is not hard to calculate; one has $$2=2^1\space\space\space 6=2^7\space\space\space 7=2^{49}\space\space\space 10=2^{23}$$ $$17=2^{47}\space\space\space 18=2^{13}\space\space\space 26=2^{41}\space\space\space 30=2^{29}$$ $$31=2^{59}\space\space\space 35=2^{11}\space\space\space 43=2^{43}\space\space\space 44=2^{17}$$ $$51=2^{53}\space\space\space 54=2^{19}\space\space\space 55=2^{37}\space\space\space 59=2^{31}$$ One can see that the sixteen exponents (in correlative position with the sixteen primitive roots) $$n\in \{1,7,49,23,47,13,41,29,59,11,43,17,53,19,37,31\}$$ are all coprimes with $60$