I am having trouble proving the following theorem from the book Number Theory Through Inquiry:

Let $p$ be a prime, $b$ an nonzero integer, and k a natural number. Then the number of $k$-th roots of $b$ modulo $p$ is either $0$ or $\gcd(k, p − 1)$.

Thoughts: I see that the question can be simplified to restricting $k$ to be a divisor of $p-1$, but I haven't been able to make further progress.

  • $\begingroup$ do you know what a group is? A field? $\endgroup$ – Will Jagy Jul 5 '16 at 20:26
  • $\begingroup$ I know some basic group theory. $\endgroup$ – OrangeApple3 Jul 5 '16 at 20:38
  • 3
    $\begingroup$ the nonzero numbers in Z/pZ are an abelian group. The map x goes to x^k makes a group, either the whole thing or a strict subgroup. $\endgroup$ – Will Jagy Jul 5 '16 at 20:41

It suffices to consider the case where $k$ is a divisor of $p-1$. Now let $q$ be a primitive root of $G=(\mathbb{Z}/p\mathbb{Z})^*$. Using Will Jagy's hint in the comments, we consider the subgroup $$H=\{q^{vk}\ |\ 1\le v\le p-1\}\subseteq G$$ Note that $q^{v_1k},q^{v_2k}\in H$ are equivalent if and only if $p-1\ |\ k(v_1-v_2)$. Thus $|H|=(p-1)/k$, where each element of $H$ is repeated $k$ times in the sequence $q^{k},q^{2k},\dots,q^{(p-1)k}$.

| cite | improve this answer | |

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.