Distribution of $n$-th roots modulo a smooth number Let $n \ge 2$. Let $p_1,\dots,p_m$ be distinct primes $\equiv 1 \pmod{n}$. Let $N=p_1 p_2 \cdots p_m$. If $\gcd(a,N)=1$ and the equation $x^n \equiv a \pmod{N}$ has a solution then it has $n^m$ solutions. This question concerns how these $n$-th roots are distributed as $a$ varies, particularly with $n$ fixed and $m$ large.
Question. Do there exist $\alpha$ and $\beta$ with $0 \le \alpha \le \beta <1$ and $\beta-\alpha$ small, such that for every $a$ coprime to $N$ that is an $n$-th power modulo $N$, there is $b$ satisfying $\alpha N \le b \le \beta N$ and $b^n \equiv a \pmod{N}$? Can we take $\beta-\alpha=O(n^{-m})$?
 A: This is a partial answer. The idea is from my recent preprint http://arxiv.org/abs/1509.03768
Additionally assuming that $p_1, \cdots, p_m$ are least among the congruence $1$ mod $n$, 
By repeated application of Linnik's theorem, there is an absolute constant $L$ such that  $N< n^{L^m}$. 
We use the following result on exponential sums over $\mathbb{Z}_N^{*}$ by J. Bourgain:
Let $N\geq 1$. For any $\epsilon>0$, there exist  a constant $\delta_0=\delta_0(\epsilon)>0$ such that for any subgroup $H$ of $\mathbb{Z}_N^{*}$ with $|H|>N^{\epsilon}$,
    $$
    \max_{(m,N)=1}\left|\sum_{a\in H}e^{2\pi i m\frac {a}N}\right|<N^{-\delta_0}|H|.$$
Note that we can use the above for any cosets of $H$. 
The set of solutions of the congruence $x^n \equiv a$ mod $N$ forms a coset of the subgroup $H$ of $\mathbb{Z}_N^{*}$ where
$$
H=\{y\in\mathbb{Z}_N^{*} | y^n \equiv 1 \textrm{ mod }N\}.$$
Taking $\epsilon = \frac{m}{L^m}$, we have $N^{\epsilon}<|H|$. 
Then by Bourgain's exponential sum result applied on the coset, and Erdős-Turán inequality, there exists $\delta(m)>0$ such that 
$$
\left||\{ 0<x<N :  x^n\equiv a (\textrm{ mod }N), \frac xN \in (\alpha,\beta) \textrm{ mod $1$} \}| - (\beta-\alpha)n^m\right|\leq n^m N^{-\delta(m)}$$
Thus, 
$$
|\{ 0<x<N :  x^n\equiv a (\textrm{ mod }N), \frac xN \in (\alpha,\beta) \textrm{ mod $1$} \}| = (\beta-\alpha)n^m +O(n^m N^{-\delta(m)}).$$
Therefore, if $N^{-\delta(m)}=o(\beta-\alpha)$, then we are guaranteed the existence of solution to $x^n\equiv a$ mod $N$  in the interval $(\alpha N, \beta N)$. 
Here's the reference: 
J. Bourgain, Exponential sum estimates over subgroups of $\mathbb{Z}_q^{*}$, $q$ arbitrary , Journal d'Analyse Mathematique, December 2005, Volume 97, Issue 1, pp 317-355.
A: Partial answer.
For $n=2$ finding the smallest solution is NP-complete
via reduction from SAT.
NP-Complete Decision Problems for Binary Quadratics p. 3

The problem of solving $ x^2 \equiv a \pmod{N}$ with natural
  solution satisfying $ 0 \le x \le \gamma$ is NP-complete.

Since this is NP-complete and $a$ depends on the SAT
instance I don't expect very sharp bounds,
might be wrong on this.
