Any hints or strategies would be greatly appreciated:

If $m$ is an integer and $b^k$ is a primitive root mod $m$, then $b$ is a primitive root mod $m$.

I am reviewing material from my elementary number theory course. I had a true/false question that I think is true (by process of elimination of how many "trues" the problem set was supposed to have). But I and am absolutely stuck on trying to prove it.

  • $\begingroup$ Welcome to the site, and please use Latex to format your equations. (Put them between a pair of $'s). $\endgroup$ – user111187 Jun 14 '14 at 21:42
  • $\begingroup$ Almost always start with the question, not your life story. $\endgroup$ – Thomas Andrews Jun 14 '14 at 21:42
  • $\begingroup$ How does your material define "primitive root"? $\endgroup$ – Thomas Andrews Jun 14 '14 at 21:45
  • $\begingroup$ Have you tried contraposition? Instead of "$b^k$ primitive $\implies$ $b $ primitive", try proving "$b $ not primitve $ \implies $ $b^k$ not primitive". $\endgroup$ – zo0x Jun 14 '14 at 21:48
  • $\begingroup$ Text is Rosen. Definition is: If $r$ and $n$ are relatively prime integers with $n > 0$ and if $ord_n r = phi(n)$, then $r$ is called a primitive root mod $n$. $\endgroup$ – Meghan K. Jun 14 '14 at 22:07

If powers of $b^k$ generate every coprime residue class mod m, then powers of $b$, which powers are a superset of the first set of powers, also generate every coprime residue class mod m. So $b$ is also a primitive root. (A coprime residue class mod m is an invertible one, i.e., $\{a|(a,m)=1\}$.)


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.