Is there any easier way to check whether $3$ is a primitive root modulo $p=65537$?

Question

What I have in mind now is that I should check for every $r|65536$, but what should I do next?

Answer 1

For $p = 65537$, $\mathbb{Z}^\ast_p$ is a group of order $p-1 = 2^{16}$. So the order of any element divides $2^{16}$, so the possible orders are $2^m$ where $m \le 16$. A primitive root is an element of order $p-1$.

If $r^{2^{15}} \neq 1 \pmod{p}$, which can be checked by $15$ squarings modulo $p$, it means that $2^{15}$ or any lower power is not the order of $r$ so it must be the case that $r$ has maximal order, and is thus a primitive root modulo $p$. So it's quite a simple check to do.

For $r=3$ we compute $3^{2^{15}} \pmod{65537}$ as $65536 \equiv -1 \neq 1$, so it indeed is a primitive root.

Answer 2

$3^{32768}\equiv -1\pmod{65537}$, so $3^{2^k}\not\equiv 1\pmod{65537}$ for $1\le k \le 15$. That suffices.