Find $\operatorname{ord}_{17} (a)$ for all $a = 1, \ldots, 16$ The  $\operatorname{ord}_{m} (a)$ is defined as the least positive integer $x$ satisfying $a^x \equiv 1 \mod m$. 
To find  $\operatorname{ord}_{17} (a)$ for all $a = 1, ..., 16,$ I know I can go through each numbers from 1 to 16 one by one (and have gotten 1, 8, 16, 4, 16, 16, 16, 8, 8, 16, 16, 16, 4, 16, 8, 2), but is there any trick to it without having to go through them one by one?
 A: You can do this: the goal is to find a generator for the group $U_{17}$, which is isomorphic to $\mathbb{Z}_{16}$.


*

*since $17 = 2^4+1$, you know that all the orders will be factors of $2^4$. 

*start with a random element of $\{1,..,16\}$, say $a=2$.

*Find $a^2$, $a^4 = (a^2)^2$, $a^8=(a^4)^2$ and so on, so that you determine the order of $a$. In this case, you get $2^2 = 4$, $2^4=16$, $2^8=1$, and $2$ has order $8$. It's not a generator, which is sad, but it still gives useful information.

*You immediately know the order of the powers of $2$. The orders of $2^1$, $2^2$, $2^3$, $2^4$, etc are $8,4,8,2,8,4,8,1$. Work out these powers. They are $2,4,8,16,15,13,9,1$. Now you have the orders of half the elements of $\{1,...,16\}$.

*The remaining elements must all be generators, with order $16$. 

A: You have $a^{16} \equiv 1$ (mod 17) with $a \not\equiv 0$ (mod 17).
So $ord_{17}(a)$ divides 16 and except 1, $ord_{17}(a) > 1$. So $ord_{17}(a)$ is even.
Take $p,q$ such that $p = -q$ (mod 17) (example (2,15),(3,14)) then $ord_{17}(p) = ord_{17}(q).$ 
A: *

*The group $\Bbb{Z}_{17}^*$ is cyclic, $a=3$ is the smallest generator (there are others, but I will use three in what follows). If you are not very familiar with the language of groups, then you may have heard the same piece of information stated as "$3$ is a primitive root modulo $17$".

*In a cyclic group of order $n$ generated by $c$ the order of the element $c^k$ is $n/\gcd(n,k)$. Here it means that the order of $3^k$ is $16/\gcd(k,16)$. To see this: You want $(3^k)^m=3^{mk}$ to be congruent to $1$. By primitive root property of $3$ this happens if and only if $mk$ is divisible by sixteen.



If you build the list in the order gotten by following powers of three, you will see a clear pattern.

A: Well, Fermat's little theorem says that the order of any number modulo $17$ must divide $16$, so it has to be a power of $2$, so you don't have to check order $3, 5, 6, 7$ and so on. They means the only operation you need is squaring. For instance, the order of $3$:
$$
3\equiv 3\\
3^2 = 9\\
3^4 = (3^2)^2 = 9^2 \equiv 13\equiv -4\\
3^8 = (3^4)^2\equiv (-4)^2 = 16\equiv -1\\
3^{16} = (3^8)^2 \equiv(-1)^2 = 1
$$It also means that apart form $1$, the order has to be an even number, so you know that $2$ and $15\equiv -2$ will have the same order, as will $3$ and $14$, and so on. This will save you some time checking.
However, the real time saver is that you can use what you find out when you're done checking one number when checking other numbers. For instance, when you checked $2$, you did
$$
2^2 = 4\\
4^2 = 16\equiv -1\\
(-1)^2 = 1
$$
then you already know that the order of $4$ is $4$ and the order of $16$ is $2$, and because of the sign thing, you know the order of $15 \equiv -2$ and $13\equiv -4$ as well. As for the checking of $3$ above, you've automatically gotten the orders of $9$ and by sign $8$, and you could've stopped when you reached $13$, because then you knew from the checking of $2$ that you needed to raise $3^4$ to an additional fourth power. So in the end, if you're keeping track, you can do all this with only $8$ squarings (including calculating $(-1)^2$ once).
A: So here are some tricks which might help to reduce the work.
If $a\neq \pm 1$ and the order of $a$ is even, then $-a(\equiv 17-a)$ will have the same order as $a$.
The numbers for which $a^r\equiv 1 \bmod m$ form a group. Therefore $a$ and $a^{-1}$ have the same order. Here you have $18\equiv 1 \bmod 17$ and $18=2\times 9=3\times 6$ so that $9$ has the same order as $2$ and $6$ has the same order as $3$. Also $35 \equiv 1$ so you can do the same trick with $5$ and $7$.
Further, if $a$ has even order, $a^2$ will have half the order of $a$.

So $1$ has order $1$ and $-1$ has order $2$.
$2$ has the same order as $15$ and $9$ and $8$
$3$ has the same order as $14$ and $6$ and $11$
$4$ has the same order as $13$ and $4^2=16\equiv -1$ so $4$ has order $4$.
$5$ has the same order as $7, 12, 10$
So we can combine these as follows. $2^2=4$ has order $4$ so $2$ has order $8$ (clearly a factor of $8$ and can't be less).
$3^2=9$ has order $8$, so $3$ has order $16$ (again easy to check can't be less).
$5^2=25\equiv 8$ has order $8$ so $5$ has order $16$ too.
This is made somewhat easier by the fact that $17-1=16$ has only the prime factor $2$, and squaring is easy. Tricks are fine for small cases, but a more systematic approach wins out in general.
