# Question from Number Theory Through Inquiry

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.

• do you know what a group is? A field? – Will Jagy Jul 5 '16 at 20:26
• I know some basic group theory. – OrangeApple3 Jul 5 '16 at 20:38
• 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. – 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}$.