I'm kind of struggling with the concept of primitive roots with non primes, specifically for $25$ in this case. I was calculating the sequences $2^x \pmod {25}$ and $3^x \pmod{ 25}$ for each $x$ up to $25$ but at $x = 20$ it starts repeating and I see that the numbers that can't be obtained are those that aren't coprime with $25$, but then I don't see how $2$, $3$ and the others can be primitive roots since there are some numbers in the residue class that you just can't obtain from the roots. What I would have concluded is that non primes simply do not have primitive roots. Am I missing something in the definition of roots here?

  • $\begingroup$ I think it is common to refer to a number $a$ as a primitive root modulo a prime power $p^n$ exactly when you get all the residue classes coprime to $p$ as powers of $a$. In other words $a$ is a generator of the group of units $\Bbb{Z}_{p^n}^*$ of the residue class ring. That last sentence may contain terms you have not yet heard - I just wanted to make this precise in a different language. Anyway, you don't appear to be missing anything. It is impossible to get residue classes divisible by $p$ as powers of those that aren't. For this reason the definition of primitive is modified. $\endgroup$ – Jyrki Lahtonen Dec 15 '14 at 11:32
  • $\begingroup$ A primitive root (if there is one) is a primitive element of $\mathbb{Z_n^{*}},\;$ and the order of this group is $\varphi(n)$. $\endgroup$ – gammatester Dec 15 '14 at 11:32
  • 1
    $\begingroup$ Oh, so that's the full definition I was lacking. I do understand the ring terminology as well so that's good. Thanks! $\endgroup$ – Snowflake Dec 15 '14 at 11:33

Powers of odd primes do have primitive roots. Moreover, if $g$ is a primitive root mod $ p$, then $g$ or $g+p$ is a primitive root mod $p^n$.

$2$ and $3$ are primitive roots mod $5$ and so one of $2,3,7,8$ is a primitive root mod $25$. It turns out that $2,3,8$ work but $7$ does not.

  • $\begingroup$ Actually, 7 is not a primitive root mod 25. $\endgroup$ – wendy.krieger Dec 15 '14 at 11:37
  • $\begingroup$ @wendy.krieger, I said "one of"... $\endgroup$ – lhf Dec 15 '14 at 11:38

Prime powers do have primitive roots. Simply adding $p$ to a known primitive root does not always guarantee a primitive root.

For example, 2 is a primitive root of 25, since it cycles through all of the twenty possible answers before returning to 1. On the other hand, 7 is not, because it only cycles through just four values (7, 24, 18, 1).

There are a smattering of primes where the smallest primitive root of p is not a primitive root of p^2, but they're pretty rare.


Using Number of consecutive zeros at the end of $11^{100} - 1$.

Multiplicative order ord$\displaystyle_{p^s}a=d\implies $ord$\displaystyle_{p^{s+1}}a=d$ or $p\cdot d$ where $p$ is an odd prime, integer $s\ge1$

ord$_5(2)=4\implies$ ord $_{25}(2)=5$ or $5\cdot4$

Now, $2^4\not\equiv1\pmod{25}\implies$ ord $_{25}(2)=5\cdot4=\phi(25)$

In fact from Order of numbers modulo $p^2$,

ord $_{25}(2+5r)=5\cdot4$ for $0\le r<5,r\ne1$

as $7^2\equiv-1\pmod{25}\implies7^4\equiv1\iff$ord$_{25}7=4$


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.