0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ $4^4\equiv 1 \bmod 17$, for the question in the title. I suppose you mean $4$, and not $45$. $\endgroup$ – Dietrich Burde Jun 17 '15 at 19:37
  • $\begingroup$ Yes, thank you. I have corrected it. Do you think that I am on the right track with my reasoning? $\endgroup$ – letsmakemuffinstogether Jun 17 '15 at 19:49
  • 2
    $\begingroup$ It is correct that the order of $a$ must divide $16$, but this is not enough. $\endgroup$ – Dietrich Burde Jun 17 '15 at 19:53
  • $\begingroup$ Why is it not enough? 17 is prime so it is coprime with every positive integer $a$ less than 17 and $4 | \phi(17)$. $\endgroup$ – letsmakemuffinstogether Jun 17 '15 at 19:55
  • 2
    $\begingroup$ It only says that the order of $a$ can only be $1,2,4,8$ or $16$. It does not say, that there exists an $a$ with order $4$. $\endgroup$ – Dietrich Burde Jun 17 '15 at 19:56
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Note that the second one can be found from the first one by exploiting $a^4 = (-a)^4$. $\endgroup$ – AlexR Jun 17 '15 at 19:46
  • $\begingroup$ I am not fluent enough with group theory to understand your answer. I am only expected to know what primitive roots are, Euler's Theorem, and some other elementary number-theoretic principles related to congruences, linear diophantine equations, and Fermat's Little Theorem. If you could please answer my question as to whether or not my reasoning is sound, that would be appreciated. Thanks. $\endgroup$ – letsmakemuffinstogether Jun 17 '15 at 19:52
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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