Number of $q$-th residues modulo $n$

81 Views Asked by At

Let $q$ be a prime and $n\ge 2$ an integer. Moreover, define $f_q(n)$ as the number of $q$-th residues modulo $n$. Is it true that if $K$ is a positive constant then there exist infinitely many $n$ such that $$ f_q(n)\le Kn? $$


I would like to add that the result holds if $q=2$, indeed it is known that $$ \limsup_{n \to \infty}\frac{f_q(n)}{n}=\frac{1}{2} \,\,\text{ and }\,\,\liminf_{n \to \infty}\frac{f_q(n)}{n}=0. $$

1

There are 1 best solutions below

4
On BEST ANSWER

If $p_1,\ldots,p_m$ are primes congruent to $1$ modulo $q$, then there are $1+(p_i-1)/q$ $q$th residues modulo $p_i$, so a proportion of $1/q + (1-1/q)/p_i$, so of about $1/q$.

Then by the Chinese Remainder Theorem, the proportion of $q$th residues modulo $n = \prod p_i$ is the product of the proportions for each prime, which is about $1/q^m$. By picking $m$ large enough you can make that proportion as small as you want.