3
$\begingroup$

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!

  • 0
    You didn't say this was $f$or a test, did you? Is there any other important information you are withholding?2012-06-28

2 Answers 2

1

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

  • 0
    Thank you for the comment in the recent deleted question, I knew what you told me already, it's really basic. it implies from solutions to $x^2-1 \equiv 0(p)$ after plugging $a^{p-1/2}$ for example. Thanks for the clarification!2012-06-28
2

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.

  • 0
    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.2012-06-28