Heh, I think I know why you are interested in this question, Harald, as Ben and I thought about essentially the same problem for what I suspect to be the same reason :-)
Anyway, we were able to get rid of the e^gamma factor. One way to proceed is to work not with the exponential sums, but rather the inner product of Lambda with Dirichlet characters. Using a Selberg sieve majorant (the same one used to prove, say, the Brun-Titschmarsh inequality) and the TT^* method, one gets a nice l^2 bound on these inner products (losing only the 2 from the parity problem, or not even that if one deletes the principal character), and then one can do some Fourier analysis on finite groups to pass from Dirichlet characters back to exponentials. It helps a little bit to smooth the sum, but it's not too essential here. (See also my paper with Ben on the restriction theory of the Selberg sieve for some related results.)
Our argument isn't written up (or checked, for that matter) yet, but we can talk more if you want to know more details.
No.
Such a bound would imply a similar bound on
$$\displaystyle \left \lvert \sum_{N(z) = M} \left(\frac{z}{w} \right)_3 \right \rvert.$$
If $M$ is a product of distinct primes $p_1,\dots p_n$ congruent to $1$ mod $3$, the norms of primes $\pi_1,\dots,\pi_n$ then $$\sum_{N(z) = M} \left(\frac{z}{w} \right)_3 = \left( \left(\frac{1}{w} \right)_3 + \left(\frac{-1 }{w} \right)_3 \right) \left( \left(\frac{1}{w} \right)_3 + \left(\frac{\omega }{w} \right)_3 + \left(\frac{\omega^2 }{w} \right)_3 \right) \prod_{i=1}^n \left( \left(\frac{\pi_i}{w} \right)_3 + \left(\frac{\overline{\pi_i} }{w} \right)_3 \right)$$
so if we choose $w$ such that $\left(\frac{-1 }{w} \right)_3 =\left(\frac{\omega }{w} \right)_3 =1$ and then choose $n$ different primes $\pi$ such that $ \left(\frac{\pi_i}{w} \right)_3 =\left(\frac{\overline{\pi_i} }{w}\right)_3$ then this will have size $6 \cdot 2^n$.
Taking $n$ sufficiently large, we contradict any bound like the one you request.
To sketch a proof of a bound, let's first understand
$$\left \lvert \sum_{z} \phi\left( \frac{ \sqrt{N(z)} - R}{T} \right) \left(\frac{z}{w} \right)_3 \right \rvert$$
where $\phi$ is a smooth bump function. The trivial bound is $O(RT)$ as we are summing over an annulus of radius $R$ and thickness $T$. Another bound is provided by integrating the Fourier transform of $\phi\left( \frac{ \sqrt{N(z)} - R}{T} \right) $ against the Fourier transform of $\left(\frac{z}{w} \right)_3 $. Since the Fourier transform of $\left(\frac{z}{w} \right)_3 $ is a bunch of Gauss sums, the same at every point, the bound we get this way will be $\sqrt{N(w)}$ times the $L^1$ norm of the Fourier transform of $\phi\left( \frac{ \sqrt{N(z)} - R}{T} \right) $.
For $T$ small, the Fourier transform of $\phi\left( \frac{ \sqrt{N(z)} - R}{T} \right) $ will look like the integral of a phase over a circle, i.e. a Bessel function, thus, viewed as a function of a complex variable $x$, approximately constant for $|x| < R^{-1}$ and proportial to $1/\sqrt{x}$ for larger values of $x$. The bump function will give us a rapidly decreasing cutoff at a radius of $1/T$.
Since the value at $0$ should be $RT$, the Fourier transform will take the value $\approx RT$ for $|x| <R^{-1}$ and $\approx R^{1/2} T / |x|^{1/2}$ for $ R^{-1} < |x| < T^{-1}$. The $L^1$ norm of this is $$ \int_{ R^{-1} }^{T^{-1} } (R^{1/2} T/ r^{1/2} ) \cdot 2 \pi r \cdot dr \approx R^{1/2} T (T^{-1})^{3/2} = (R/T)^{1/2} $$ so we get
$$\left \lvert \sum_{z} \phi\left( \frac{ \sqrt{N(z)} - R}{T} \right) \left(\frac{z}{w} \right)_3 \right \rvert \ll \min ( RT, (R N(w) /T)^{1/2} )$$
Now in the sharp cutoff case we can express the characteristic function interval of radius $\sqrt{A}$ and thickness $B/ \sqrt{A}$ as a sum of smoothed characteristic functions of the same radius and dyadically decreasing thickness. So the bound we get will be obtained by summing the bounds for (dyadically) different values of $T$ from $0$ to $B/\sqrt{A}$, and thus will be comparable to the bound for the worst case of $T$.
The worst case occurs when the two terms in the minimum are equal, $ RT= (R N(w) /T)^{1/2}$, or $T = (N(w)/ R)^{1/3}$, giving a bound of $$ R^{2/3} N(w)^{1/3} = (A N(w))^{1/3},$$ in other words, by working out the details, I believe it should be possible to prove a bound of the form
$$\displaystyle \left \lvert \sum_{A < N(z) < A + B} \left(\frac{z}{w} \right)_3 \right \rvert \ll (A N(w))^{1/3}$$
This gives cancellation for $A \gg N(w)^{1/2}$, so we still obtain cancellation in intervals of greater than square-root size, which makes sense as this is possible in the classical setting (https://arxiv.org/abs/1508.00512), but not as much cancellation for larger intervals, which also makes sense as the boundaries in this setting are less smooth than in the classical one.
Best Answer
If $\gcd(c,d) = 1$ we have
$$\displaystyle \left \lvert \{b \pmod{d} : b^k \equiv c \pmod{d} \}\right \rvert = \sum_{\substack{\chi \pmod{d} \\ \chi^k = \chi_0}} \chi(c).$$
This is not really anything to do with numbers - it works in any finite abelian group, and here we are applying it to the multiplicative group of invertible residue classes mod $c$.
It's a consequence of orthogonality of characters for the group $G/ G^k$.