0
$\begingroup$

Ive been asked to prove by induction that no primitive roots exist modulo $2^n$ for n $\geq$ 3.

I have proven true for base case $n=3$, and assumed to be true for $n$. I'm now stuck at this point:

$${x^{2}}^{n-1} \equiv 1 \pmod{2^{n+1}}.$$

thank you :)

$\endgroup$
5
  • 2
    $\begingroup$ If there were a primitive root mod $2^{n + 1}$ then that same root would be a primitive root mod $2^n$. $\endgroup$
    – WhatsUp
    Oct 31, 2021 at 21:51
  • $\begingroup$ hey man, thanks for the help- im still struggling to see how i can use that to prove the induction as im trying to prove it for $2^{n+1}$ not $2^{n}$? Sorry as you can tell this isnt a strong area of mine, thanks again for the help $\endgroup$
    – georgielee2000
    Oct 31, 2021 at 22:54
  • $\begingroup$ Forward-backward induction of Cauchy? Assume $n$ and prove $n-1$ $\endgroup$
    – kelalaka
    Oct 31, 2021 at 23:09
  • $\begingroup$ If it exists for $n+1$, it exists for $n$. By the contrapositive and since we know it doesn’t exist for $n$, it doesn’t exist for $n+1$. $\endgroup$
    – Eric
    Oct 31, 2021 at 23:18
  • $\begingroup$ Use induction on $n\ge 3$. Let $n'=n+1$. Show that if $x^{2^n-2}\equiv 1\pmod {2^n}$ whenever $x$ is odd, then $x^{2^{n'}-2}$ $\equiv 1$ $\pmod {2^{n'}}.$ $\endgroup$
    – DanielWainfleet
    Nov 1, 2021 at 8:39

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .