Sums of powers mod p For prime $p > 7$ with $p-1=rs$, $r>1$, $s>1$, let $A=\{x^r|x \in \mathbb{Z}_p\}$ and $B = \{x^s|x \in \mathbb{Z}_p\}$. If $g$ is a primitive root mod $p$ then $A = \{0\} \cup \{g^{ir}|0 \leq i < s \}$ and $B = \{0\} \cup \{g^{js}|0 \leq j < r \}$.  Is it always true that $\mathbb{Z}_p \neq A + B$?
 A: For fixed $r>1$, use of Weil's bound will give the result. 
    We refer to Theorem 5.1 from chapter 2 of W.M.Schmidt, Equations over Finite Fields: An Elementary Approach.
Theorem
    Let $f_1,\cdots, f_n$ be polynomials with coefficients in $\mathbb{F}_q$ and of degree $\leq m$. Put $\delta=\textrm{lcm}(d_1,\cdots,d_n)$, and $d=d_1d_2\cdots d_n$. Let X be a variable and let $\eta_1,\cdots,\eta_n$ be algebraic quantities with
    \begin{equation}
    \eta_1^{d_1}=f_1(X), \cdots, \eta_n^{d_n}=f_n(X).\
    \end{equation}
    Suppose
    \begin{equation}
    [\overline{\mathbb{F}}_q(X, \eta_1,\cdots,\eta_n):\overline{\mathbb{F}}_q(X)]=d.
    \end{equation}
    Then if $q>100\delta^3m^2n^2$, the number $N$ of solutions $(x,y_1,\cdots,y_n)\in\mathbb{F}_q^{n+1}$ of the equations $y_1^{d_1}=f_1(X),\cdots,y_n^{d_n}=f_n(X)$ satisfies
    \begin{equation}
    |N-q|<5mnd\delta^{5/2}q^{1/2}.
    \end{equation} 
    We will use this theorem to solve the problem for fixed $r>1$. We have $q=p$ prime number. Let $g$ be a primitive root modulo $p$. We put $n=r+1$, $m=1$, $d_1=\cdots=d_n=r$, $\delta=r$, $d=r^{r+1}$, $f_i(X)=g(X-g^{is})$ for $0\leq i \leq r-1$, and $f_r(X)=gX$. Then the condition is satisfied, and the number $N$ of solutions to the system $Y_i^r=f_i(X)$ ($0\leq i \leq r$) is 
    \begin{equation}
    |N-p|<5(r+1) r^{r+1+5/2}p^{1/2}.
    \end{equation}
We look for the number $N^{*}$ of solutions with no $Y_i$ being zero. 
Then we have
$$N^{*}\geq p-5(r+1) r^{r+1+5/2}p^{1/2}-(r+1)r^{r+1}.$$ 
This is in fact greater than zero for sufficiently large $p$. For any such solution $(X,Y_0,\cdots, Y_r)\in \mathbb{F}_p^{r+2}$, we obtain that
$$X\in \mathbb{Z}_p-(A+B).$$ 
This proves the result. 
A: This is a very partial answer, addressing the extreme cases $r=2$ and $r=s$ only. 
For $r=s$ we have $A=B$ and $|A|=|B|=r+1$. Hence 
  $$ |A+B|\le \binom{r+1}2+(r+1)=\frac{p+3r+1}{2} < p, $$ 
implying $A+B\ne{\mathbb F_p}$. 
This trivial argument extends onto the case where $r$ and $s$ have a sufficiently large greatest common divisor. Namely, writing $d=(r,s)$, we have $|A\cap B|=d+1$; it follows that at least $(d+1)^2-\binom{d+1}2=(d+1)(d+2)/2$ sums $a+b$ are wasted on double representations. Therefore 
  $$ |A+B|\le |A||B|-\frac{(d+1)(d+1)}2=p+r+s-\frac{(d+1)(d+2)}2; $$
as a result, if $(d+1)(d+2)>2(r+s)$, then $A+B\ne{\mathbb F}_p$.
For $r=2$ the problem reduces to showing that for any sufficiently large prime $p$, there is a run of three consecutive quadratic non-residues $\mod p$. This is easy to prove using Weil's bound, but can be done in an elementary way, as follows.
The following argument actually works for all $p\ge 11$. Suppose, for a
contradiction, that for any $z\in{\mathbb F}_p$, at least one of $z,z-1$, and
$z+1$ is a square. Then
  $$ \Big(\Big(\frac{z-1}p\Big)-1\Big)
     \Big(\Big(\frac{z}p\Big)-1\Big)
     \Big(\Big(\frac{z+1}p\Big)-1\Big) = 0 $$
for every $z\in{\mathbb F}_p$, except that if
$\Big(\frac{-1}p\Big)=\Big(\frac{-2}p\Big)=-1$, then for $z=-1$ this product
is equal to $-4$. Letting $\delta=1$ in this case and $\delta=0$ otherwise,
we thus have
  $$ \sum_{z\in\mathbb F_p}
     \Big(\Big(\frac{z-1}p\Big)-1\Big)
     \Big(\Big(\frac{z}p\Big)-1\Big)
     \Big(\Big(\frac{z+1}p\Big)-1\Big) = -4\delta. $$
Opening the parentheses and evaluating "quadratic sums" yields
  $$ \sum_{z\in{\mathbb F}_p} \Big(\frac{(z-1)z(z+1)}p\Big) = (p-3) - 4\delta. $$
This shows that for all $z\in{\mathbb F}_p\setminus\{-1,0,1\}$, writing for
brevity $f(z)=(z-1)z(z+1)$, we have $\Big(\frac{f(z)}p\Big)=1$, save for
exactly $2\delta$ exceptional values of $z$. Observing that $f(-z)=-f(z)$, we
conclude that $\Big(\frac{-1}p\Big)=1$; hence $\delta=0$, meaning that,
indeed, $\Big(\frac{f(z)}p\Big)=1$ for all $z\in{\mathbb
F}_p\setminus\{-1,0,1\}$, without any exceptions.
What we have shown so far is that $f(z)$ is a quadratic residue for each
$z\in{\mathbb F}_p\setminus\{-1,0,1\}$. Consequently, so is
$f(z+1)/f(z)=(z+2)/(z-1)=1+3/(z-1)$, an evident nonsense!
