Primitive roots of $25$

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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$