deciding whether $125$ is a primitive root modulo $529$ I'd like your help with the following: I need to show that $5$ is a primitive root modulo $23^m$ for all natural $m$ and to decide if $125$ is a primitive root modulo $529$.
For the first part I need to show that $5$ is a primitive root for $23$ ( I showed that) and that $5^{22} \neq 1\pmod{23}$ in order to use the theorem which says that if $g$ is a primitive root modulo $p$ it is also a primitive root for modulo $p^l$ for all natural $l$, but how can I compute $5^{22}$ modulo $23^2$ and show that it does not equal $1$?
Also for I'd love help for the second part of the question- What can help me determining whether $5^2$ is a primitive root $529$? I couldn't find any theorem or simple way to for showing it. If I remember correct I read somewhere that $ord_m{g^c}= \frac{ord_mg}{\gcd(c,\phi(m))}$. Is this correct and the best way to determine the claim? If so, how can I prove it? 
Thanks a lot!
 A: In general, to compute $a^b\pmod m$, you either 1) find some software designed to do this calculation in a split second, or 2) you write $b$ in binary and use that to express $a^b$ as a small number of squarings and multiplications by $a$, and at every stage along the way you reduce modulo $m$ so you never have to deal with numbers exceeding $m^2$. 
EDIT: for the additional question, $5^2$ can't possibly be a primitive root, since $(5^2)^{253}=5^{506}\equiv1\pmod{529}$, so $5^2$ is of order at most 253. 
A: Here's one way of doing it with pencil and paper calculations. Essentially I do a test
run of the algorithm implicit in Gerry's answer.
$$5^4=625=529+96\equiv 96\pmod{529}.$$
This implies
$$5^5\equiv5\cdot96=480\equiv-49\pmod{529}.$$
Squaring this gives
$$
5^{10}\equiv(-49)^2=2401=2116+285\equiv285\pmod{529}.
$$
So
$$
5^{11}\equiv5\cdot285=1425=1058+367\equiv367\pmod{529}.
$$
As a check (scanning for errors is a good habit to acquire!) we observe that $367\equiv-1\pmod{23}$.
At this point we are done. We know from general theory that $\mathbb{Z}_{529}^*$
is cyclic of order $\phi(529)=506$. Therefore there are exactly two residue
classes $x$ modulo $529$ that are solutions of the equation $x^2=1$, namely
the cosets of $\pm1$. As $367$ is not one of them, we know that 
$$5^{22}=(5^{11})^2\equiv(367)^2\not\equiv1\pmod{529}.$$
For the last part I would first check, whether the following basic fact about cyclic groups might help? If $G=\langle g\rangle$ is a cyclic group of order $n$, then
$g^m$ is another generator of $G$ if and only if $\gcd(m,n)=1$. This is part of the
result that you quoted. In a typical first course of abstract algebra that result is
proved shortly after cyclic groups and subgroups have both been introduced. I would be very surprised, if it was not covered in your course. The proof uses the division algorithm of integers (=a single step in Euclid's algorithm).
