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
-
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$