Determining whether there exists an $a$ such that $\text{ord}_{17}(a) = 4$.

Question

I am trying to determine whether there exists an $a$ such that $\text{ord}_{17}(a) = 4$, where $\text{ord}_{17}(a)$ is the least integer $k$ such that $a^k \equiv 1\pmod{\! 17}$. This is equivalent to determining whether or not there exists an $a \in \mathbb{Z}$ such that $a^4 \equiv 1\pmod{\! 17}$.

My strategy is to notice that if $\gcd(a,n) = 1$ and $n>0$, then $\text{ord}_n(a)\mid \phi(n)$. In this case, we have $4\mid 16$, so then it follows there exists an $a$ such that $\text{ord}_{17}(a) = 4$. Is my reasoning sound?

Answer 1

Your reasoning is not sound. Look again at the theorem you wrote:

if $\gcd(a,n)=1$ and $n>0$, then $\text{ord}_n(a)\mid \varphi(n)$.

The only way you can imply anything using this statement is using the 'if' part. $4\mid \varphi(17)$ is irrelevant to the 'if' part.

Using only the theory you say you know in the comments:

$\exists\, g:\, \text{ord}_{17}(g)=16\,$ (i.e. primitive root mod $17$).

Then $\text{ord}_{17} \left(g^4\right)=4$. If you can prove this, you're done.

In fact, it is enough to show $\text{ord}_{17}(4)=4$, which is done simply by showing $$4^4\equiv 1,\, 4^2\not\equiv 1\pmod{\! 17}$$

I didn't check $4^3, 4^1$ because more generally:

$$\text{ord}_p(a)=k\iff (a^k\equiv 1\!\!\pmod{\! p}\ \text{ and }\ q\mid k\,\Rightarrow\, a^{k/q}\not\equiv 1\!\!\pmod{\! p})$$

Generalization to your problem (proved similarly) is:

$h\ge 1,\ h\mid p-1\implies\, \exists\, a\,$ such that $\,\text{ord}_p (a)=\frac{p-1}{h}$

Answer 2

One does exist, that is because the multiplicative group of $\mathbb Z_p$ is isomorphic to $\mathbb Z_{p-1}$ So in this case the multiplicative group is isomorphic to $\mathbb Z_{16}$. It is a well known fact a cyclic group $\mathbb Z_n$ has $\varphi(d)$ elements of order $d$ for any $d$ dividing $n$. So there should be $2$ elements of order $4$.

In this case finding one is simple, just take an element and look at the generated subgroup, it must contain an element of order $4$ (Unless you picked $15$ or $1$ at the start.

Using this strategy I found $4$ and $13$ are the elements you are looking for.

Answer 3

$G=\mathbb{F}_{17}^*$ is a group with sixteen elements, and $n\mid 16$ is a necessary condition for $a\in G$ to have order $n$ (by Lagrange's theorem). It is also a sufficient condition since $G$ is a cyclic group: $$\exists g\in G:o(g)=o(G)=16$$ hence for any $g\in G$ fulfilling the above line, $g^4$ has order $4$ as wanted.

Notice that ciclicity is crucial. $\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{Z}_2$ has sixteen elements, too, but no element of order four.

Moreover, since $17$ is a prime of the form $2^n+1$, every non-quadratic residue in $\mathbb{F}_{17}$ is an element of order $16$ in $\mathbb{F}_{17}^*$. Since $17$ is a prime of the form $3k+2$, $-3$ is a non-quadratic residue and $$ (-3)^4 \equiv 81 \equiv \color{red}{-4} \pmod{17}$$ is an element with order four. The other one is $\color{red}{4}$.

Answer 4

Yes, that's right. Also, in general, there exists a primitive element in mod $ n$ if and only if $n$ is one of the numbers/forms $1,2,4,p^k,2p^k$, where $p$ is an odd prime, and $k$ is a positive integer. By primitive element, I mean an element of order $\phi(n)$. So, in such cases, an element of order $d$ exists if and only if $d$ divides $\phi(n)$, by just considering the primitive element.