Show that 7 is a primitive root modulo 601 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.
 A: 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.
A: 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$.
