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!

  • $\begingroup$ 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$. $\endgroup$ – Gerry Myerson Jun 28 '12 at 6:17
  • 2
    $\begingroup$ $125^{506} = 1 \mod 23^2$ by Euler-Fermat. I don't think that's what you want. $\endgroup$ – Cocopuffs Jun 28 '12 at 6:18
  • $\begingroup$ @Cocopuffs: so right, my bad. Thanks, I corrected it. $\endgroup$ – Jozef Jun 28 '12 at 6:24
  • $\begingroup$ @GerryMyerson:Thank you for the suggestion. I don't have a computer in the test sadly. $\endgroup$ – Jozef Jun 28 '12 at 6:25
  • $\begingroup$ You didn't say this was for a test, did you? Is there any other important information you are withholding? $\endgroup$ – 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).

  • $\begingroup$ 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$ $\endgroup$ – Jyrki Lahtonen Jun 28 '12 at 7:35
  • $\begingroup$ 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. $\endgroup$ – Jozef Jun 28 '12 at 7:36
  • $\begingroup$ YW, @Jozef. You do remember that $125=5^3$, not $5^2$. $\endgroup$ – Jyrki Lahtonen Jun 28 '12 at 7:38
  • $\begingroup$ 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! $\endgroup$ – Jozef Jun 28 '12 at 7:45
  • $\begingroup$ @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 :-) $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – Jozef Jun 28 '12 at 6:30
  • $\begingroup$ 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. $\endgroup$ – Gerry Myerson Jun 28 '12 at 6:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.