# 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!

-
You mean to say that you have to prove $5^{22}\not\equiv1\pmod{23^2}$, and use the theorem about modulo $p^2$. Anyway, it shouldn't be hard to get a computer to find $5^{22}$ and tell you the remainder on division by $23^2$. – Gerry Myerson Jun 28 '12 at 6:17
$125^{506} = 1 \mod 23^2$ by Euler-Fermat. I don't think that's what you want. – Cocopuffs Jun 28 '12 at 6:18
@Cocopuffs: so right, my bad. Thanks, I corrected it. – Jozef Jun 28 '12 at 6:24
@GerryMyerson:Thank you for the suggestion. I don't have a computer in the test sadly. – Jozef Jun 28 '12 at 6:25
You didn't say this was for a test, did you? Is there any other important information you are withholding? – Gerry Myerson Jun 28 '12 at 6:59

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).

-
You can pick your favorite route to $5^{11}$. I just happened to notice that $-49$ came out at $5^5$, and because I did a lot of mental arithmetic in my adolescence, I had its square in zero time. If you have done less of that, then you can also quickly calculate it: $(50-1)^2=\cdots$ – Jyrki Lahtonen Jun 28 '12 at 7:35
Thanks Jyrki, that was what I eventually did. I guess that Gerry's point about $5^2$ not being primitive root is true and simple as it can be, so I'll adopt it. – Jozef Jun 28 '12 at 7:36
YW, @Jozef. You do remember that $125=5^3$, not $5^2$. – Jyrki Lahtonen Jun 28 '12 at 7:38
Oh no! so it's not true, I made a mistake and made Gerry do a mistake. O.k I'll think of what you wrote. Thanks for the important correction! – Jozef Jun 28 '12 at 7:45
@Jozef: You first asked, whether $125$ is a primitive root, and later you asked whether $5^2$ is. I think that Gerry was responding to the latter question. I am answering to the first :-) – Jyrki Lahtonen Jun 28 '12 at 7:49

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.

-
Thank you for the answer, but I don't have computer in my test, even though it looks like a nice job to write a code for this problem. – Jozef Jun 28 '12 at 6:30
The point of the second method is that you don't need a computer. If you can't write 506 in binary by hand (and I notice you have edited out the part of the question that asked for $125^{506}\pmod{529}$), or if you can't multiply two three-digit numbers by hand, or if you can't divide a 6-digit number by a 3-digit number and get the remainder by hand, then you can't find $125^{506}\pmod{529}$ by hand --- but if you can do those things, the method I give works like a charm. – Gerry Myerson Jun 28 '12 at 6:58