0
$\begingroup$

Im trying to prove that an odd primitive root mod an odd prime is also a primitive root for two times that modulus.

Im just not sure exactly how to go about this. I've tried expressing $a^k\equiv1 modP$ as $a^k=1+Pk$ to try to reach an equation that makes sense for 2P. I just feel like Im not going about this the right way.

$\endgroup$
0
$\begingroup$

Let $a$ be a primitive root modulo $p$ for a odd prime $p$. A integer $a$ is a primitive root modulo $m$ if $$a^{\varphi(m)} \equiv 1 \pmod m$$ and $\varphi(m)$, the number of integers less than $m$ and coprime with $m$, is the smallest positive integer for what this equation holds. As a result of Euler's Theorem, we have:

$$a^{\varphi(p)} \equiv 1 \pmod p$$

Because we know that $a$ is a primitive root modulo $p$, we know that $\varphi(p)$ is the smallest positive integer for which the equation holds. By hypothesis, $a$ is odd, so we also know that

$$a^{\varphi(p)} \equiv 1 \pmod 2$$

Thus, by the Chinese Remainder Theorem, we must have that:

$$a^{\varphi(p)} \equiv a^{\varphi(2p)} \equiv 1 \pmod{2p}$$

Note that first equality follows from multiplicative property of the $\varphi$ function: $\varphi(2p) = \varphi(p)$ for odd primes $p$. Now, suppose that, for a positive integer $n$, we have:

$$a^n \equiv 1 \pmod{2p}$$

By the Chinese Remainder Theorem, that would imply:

$$a^n \equiv 1 \pmod{p}$$

We know that the least such integer is $\varphi(p)$, so $n \geq \varphi(p)$. Therefore, $n \geq \varphi(2p)$, and that concludes the proof.

$\endgroup$
  • $\begingroup$ This isn't correct. $a$ itself doesn't have to be coprime with $\phi(p)=p-1$. There are lots of primes for which $a=2$ is a primitive root, for example. $\endgroup$ – Greg Martin Jun 1 '16 at 3:39
  • $\begingroup$ @GregMartin you are correct, I forgot about that. It must be coprime with $\varphi(\varphi(p))$ right? Because of the group isomorphism. I'll correct it now. $\endgroup$ – Henrique Augusto Souza Jun 1 '16 at 3:50
  • $\begingroup$ @GregMartin I believe that the algebraic proof is correct now. I have also missed the odd root hypothesis, which made me even the more wrong. $\endgroup$ – Henrique Augusto Souza Jun 1 '16 at 4:01
  • $\begingroup$ The first part is still not correct (again, think of $a=2$). I recommend deleting it entirely. The second proof is correct, though the wording could be improved. Proving that $a^{\phi(2p)}\equiv1\pmod{2p}$ uses the Chinese remainder theorem and Fermat's little theorem modulo $p$; proving that $a^k\not\equiv1\pmod{2p}$ for any $1\le k\le \phi(2p)$ follows from considering the congruence modulo $p$ and using the fact that $a$ is a primitive root. $\endgroup$ – Greg Martin Jun 1 '16 at 5:53
  • 1
    $\begingroup$ @GregMartin now I see. The second condition involves the image of the primitive root on the corresponding additive group (the discreet logarithm). On a more general notion, all I needed to do was show that $a$ was the generator of the multiplicative group, and that there was a natural isomorphism between $\mathbb{Z}/2p\mathbb{Z}^\times$ and $\mathbb{Z}/p\mathbb{Z}^\times \times \mathbb{Z}/2\mathbb{Z}^\times$. Between the arithmetic proof and the algebraic proof using that discreet logarithm, I now think that the arithmetic one is more accessible. Thanks for your suggestions! $\endgroup$ – Henrique Augusto Souza Jun 1 '16 at 6:14

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.