# Primitive Root mod 26 and 25?

I would live to calculate the primitive roots modulo 26 and modulo 25.

My approach: 26 is not a prime number. But 26=2*13 are Prime numbers. So I calculated the primitive roots of them: Result for 2: 1 Result for 13: 2,6,7,11

So what are the primitive roots of 26? For 25 I know that 25=5*5. But I dont know how it helps.

• A primitive root modulo $q$ is, by definition, an element of (multiplicative) order $\phi(q)$. What is $\phi(26)$, and what integers have order $\phi(26)$ modulo $26$? (Hint: there are four residue classes of primitive roots modulo $26$, and $7$ is one of them.) Same with $25$: what is $\phi(25)$...? – Greg Martin Dec 18 '14 at 7:31
• – lab bhattacharjee Dec 18 '14 at 8:53
• I tried it as Greg Martin suggested. My result: primitive roots of 26 are: 7,11,15,19 and primitive roots of 25 are 2,3,8,12,13,17,22,23. Is that right? phi(25) = 20 and phi(26) = 12. – NumberTheory Dec 18 '14 at 9:14

If ord$\displaystyle_pa=d$ and ord$_2a=1$ if $a$ is odd and $p$ is an odd prime

we can prove that ord$_{2p}a=$lcm$(d,1)=d$

So, if ord$_pa=\phi(p)=p-1$ or ord$_{2p}(a+r\cdot p)=p-1=\phi(2p)$ if $a+r\cdot p$ is odd , where $0\le r<p$

More specifically, if $a$ is a primitive root $\pmod p$

Case $\#1:$ if $a$ is odd and $a$ will be a primitive root $\pmod {2p}$

Case $\#2:$ Else i.e., if $a$ is even, $a+p$ will be a primitive root $\pmod {2p}$

• For the sake of completeness: if $a$ is a p.r. mod $p$ and $a^{p-1}\not\equiv1\pmod{p^2}$ then $a$ is a p.r. mod each $p^k$. If $a^{p-1}\equiv1\pmod{p^2}$, replace $a$ by $a+p$ s.t. $(a+p)^{p-1}\not\equiv1\pmod{p^2}$ and $a+p$ is a p.r. mod each $p^k$. – punctured dusk Dec 22 '14 at 19:27