Counting the number of solutions of the congruence $x^k\equiv h$ (mod q)

Question

Let (h,q)=1, I would like to prove that for any $\epsilon>0$, $$ |\{0\leq x<q:x^k\equiv h(\text{mod q})\}|<C(\epsilon)q^\epsilon $$ for some constant $C(\epsilon)$ depending on $\epsilon$. The first thing to observe is $(x,q)=1$. I tried to extract something from the equation $a^k\equiv b^k$(mod q), while the only thing I can see is that this can't happen if $|a^k-b^k|<q$, due to my lack of knowledge. But this is far away from the answer. I have also tried to factor out $q=p_1^{e_1}...p_k^{e_k}$ and only consider modulo a prime power, but I doubt if it works, even if it works I still don't have an idea how to solve the case even when q is a prime.

Thanks in advance for your time and effort. For a reference to this problem, see page 72 in Vaughan's book, The Hardy-Littlewood Method.

Answer 1

Even when doing elementary modular arithmetic, you must know at least the basic properties of the ring $\mathbf Z/q\mathbf Z$, in particular the Chinese remainder theorem: if $q={p_1}^{e_1}...{p_r}^{e_r}$ (product of powers of distinct primes), there is a ring isomorphism $\mathbf Z/q\mathbf Z \cong \mathbf Z/{p_1}^{e_1}\mathbf Z \times ...\mathbf Z/{p_r}^{e_r}\mathbf Z$, which implies in particular an isomorphism of multiplicative groups $(\mathbf Z/q\mathbf Z)^* \cong (\mathbf Z/{p_1}^{e_1}\mathbf Z)^* \times ...(\mathbf Z/{p_r}^{e_r}\mathbf Z)^*$, where $(\mathbf Z/n\mathbf Z)^*$ denotes the group of invertible elements of the ring $\mathbf Z/n\mathbf Z$. Given $(h,q)=1$, to solve $x^k \equiv h$ mod $q$ is then equivalent to solve ${[x_i]}^k=[h_i]$ in ($\mathbf Z/{p^{e_i}}\mathbf Z)^*$ for all $i=1,..., r$, where $[y_i]$ denotes the class of $y$ mod ${p_i}^{e_i}$.

We are thus brought back to solve @ ${[x_i]}^k=[h_i]$ in $(\mathbf Z/{p^{e_i}}\mathbf Z)^*$. The structure of the latter group is known : it is cyclic of order $\phi({p^{e_i}})$ (where $\phi$ is the Euler function), except when $p=2, e_i\ge 3$, in which case it is $\cong (\mathbf Z/2\mathbf Z,+)\times (\mathbf Z/2^{e_i-2}\mathbf Z,+)$. For simplicity, we'll consider only the cyclic case (the exceptional non cyclic case is just a matter of book keeping), and use repeatedly the fact that a cyclic group of order $g$ admits a unique subgroup of order $g'$, for any $g'$ dividing $g$. Denote by $ord (.)$ the order of an element in a group. Here in $(\mathbf Z/{p^{e_i}}\mathbf Z)^*$, @ admits a solution iff $ord[x_i]=k.ord [h_i]$ divides $\phi({p^{e_i}})$. If such is the case, the number of solutions of @ is also the number of solutions of ${[y_i]}^k=1$, i.e. $k$.

In conclusion, in the non exceptional case, suppose moreover that $q$ is odd (just to avoid petty book keeping). The original congruence in $(\mathbf Z/q\mathbf Z)^*$ admits a solution iff $k.ord [h_i]$ divides $\phi({p^{e_i}})$ for $i=1,...,r$, in which case the total number of solutions is $k^r$.

Answer 2

Oh, if this is that , it has not any "fundamental" character. But it is worth coming back to the proof to see precisely what conditions are needed. To speak of roots of a polynomial, you need to work at least in a ring $R$ (with 2 operations, + and $\times$). Your polynomial $f(X)\in R[X]$ then reads $f(X)=a_n X^n +...+a_0$, where $a_i \in R$ . The usual proof of the "fundamental thm." starts like this: if $y\in R$ is a root of $f$, then $(X-y)$ must divide $f(X)$. But how do you prove this lemma ? If you think of it, the only known way is to use euclidian division in $R[X]$, i.e. $f(X)=(X-y)g(X)+r$, the key point being that the degree of the remainder $r$ must be strictly less than the degree of the divisor, so that here $r\in R$, hence $r=0$ if $y$ is a root. But to perform euclidian division, at least you have to divide by non zero coefficients at some point, i.e. you need an extra operation, namely division, which turns your ring into a field. Starting from a ring $R$ which is a domain (i.e. $xy=0$ implies $x$ or $y=0$), you can embed $R$ into its field of fractions, but not all rings are domains. For instance, $Z/nZ$ is a domain iff $n$ is prime, iff $Z/nZ$ is a field.

Actually, the original question in your post is not field theoretical. The Chinese remainder thm. is ring theoretical, but from that on, the rest of the study is purely group theoretical.