1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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)$...? $\endgroup$ – Greg Martin Dec 18 '14 at 7:31
  • 1
    $\begingroup$ For $25,$ see math.stackexchange.com/questions/992688/primitive-root-mod25 $\endgroup$ – lab bhattacharjee Dec 18 '14 at 8:53
  • 1
    $\begingroup$ 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. $\endgroup$ – NumberTheory Dec 18 '14 at 9:14
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – punctured dusk Dec 22 '14 at 19:27

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.