How to prove 2 is a primitive root mod 37, without calculating all powers of 2 mod 37?

Question

How can i prove 2 is a primitive root mod 37, without calculating all powers of 2 mod 37?

Answer 1

The order of any element in an order 36 group is a factor of 36 (Lagrange's theorem), so it suffices to check $2^a \not\equiv 1\pmod{37}$ for $a \in \{1, 2, 3, 4, 6, 9, 12, 18\}$.

But in fact that can be reduced further: if $2^a \equiv 1\pmod{37}$ then $2^{ab} \equiv 1\pmod{37}$, so the tests can be reduced to $a \in \{12, 18\}$.

Answer 2

As Peter Taylor explained, it suffices to verify that neither $2^{12}$ nor $2^{18}$ is congruent to $1$ modulo $37$.

If $2^{18}$ were $\equiv1\pmod{37}$, then (because there exists a primitive root) two would have to be a quadratic residue modulo $37$. But $37\equiv 5\pmod8$, so one of the supplements to the law of quadratic reciprocity tells us that this is not the case.

That leaves $2^{12}$. Here I recommend lab's way: $2^6\equiv-10$, so $2^{12}\equiv(-10)^2=100\not\equiv1$. Case closed.

---

In general similar techniques can be used to check whether a given number is a primitive root modulo a prime $p$, if you can fully factor $p-1$. Assume that we have the factorization $$ p-1=\prod_jq_j^{a_j}, $$ where $a_j$ are positive integers, and $q_j$ are primes for all $j$. Then we can conclude that $a$ is a primitive root, iff $a^{(p-1)/q_j}\not\equiv1\pmod p$ for all $j$. This is because all the proper factors of $p-1$ are factors of at least one of the numbers $(p-1)/q_j$. In the case $q_j=2$ we can try and use the law of quadratic reciprocity instead. To that end we need to be able to factor $a$. We can also always use the square-and-multiply algorithm to calculate high modular powers relatively efficiently.