Show that 7 is a primitive root modulo 601

Question

How do you show that 7 is a primitive root modulo 601 without having to do many, many congruences? I'm sure there is an easier way and I should like very much to learn it.

Answer 1

Because $601$ is a prime, the group $\Bbb{Z}_{601}^*$ has order $600$. By Lagrange, the order $e$ of $7$ in this group is a factor of $600=2^3\cdot3\cdot5^2$.

You want to prove that $e=600$, which amounts to showing that no proper factor $d\mid 600, d<600,$ will have the property $7^d\equiv1$. All such numbers $d$ are, in turn, factors of $600/p$ for some prime $p\mid 600$. Furthermore, if $d\mid (600/p)$ and $7^{600/p}\not\equiv1$, then $7^d$ cannot be congruent to $1$ either.

Therefore it suffices to test whether any of $7^{300}$, $7^{200}$ or $7^{120}$ is congruent to $1\pmod{601}$. You can calculate those residue classes relatively quickly by square-and-multiply.

Answer 2

Note that $601$ is prime, so the question is if $7^k\equiv n$ has a solution for any $n\in \Bbb{N}$.

By fermat's little theorem, $7^{601}\equiv 7$ (mod 601).

Now comes the trick: let $a$ be the lowest power of $a$ greater than $1$ for which $7^a\equiv 7$.

Proof $a$ divides $601$: If $a$ doesn't divide $601$, then by the division algorithm, $601=aq+r$ where $q\in\Bbb{N}$ and $0<r<a$. This implies $7^{aq+r}\equiv 7$, so $(7^a)^q7^r\equiv7^{q+r}\equiv 7$. However, it is clear that $q+r$ is between $1$ and $601$, which is a contradiction. Thus $a$ divides $601$.

Since $601$ is prime, we see that $7^{601}$ is the first power of $7$ congruent to $7$ after $1$.

This also shows that there can be no distinct values $a,b$ between $1$ and $601$ for which $7^a\equiv 7^b$ (this would in turn imply a value between $1$ and $601$ for which $7$ to that power is congruent to $1$, and thus one plus that power is congruent to $7$, which we already disproved.

In summary, we have shown that the $7^k$ maps to 600 distinct values — all values in $\Bbb{Z}_{601}$. Thus $7$ must be a primitive root.

---

tl;dr:

Define a function $f(k)=7^k$. Show that this function is injective and show that $f$ is a bijection by showing it is surjective onto integers modulo $601$.