For prime $p > 7$ with $p1=rs$, $r>1$, $s>1$, let $A=\{x^rx \in \mathbb{Z}_p\}$ and $B = \{x^sx \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$?

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 AB\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 nonresidues $\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,z1$, and $z+1$ is a square. Then $$ \Big(\Big(\frac{z1}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{z1}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{(z1)z(z+1)}p\Big) = (p3)  4\delta. $$ This shows that for all $z\in{\mathbb F}_p\setminus\{1,0,1\}$, writing for brevity $f(z)=(z1)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)/(z1)=1+3/(z1)$, an evident nonsense! 


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} Nq<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(Xg^{is})$ for $0\leq i \leq r1$, 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} Np<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 p5(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. 

