Shifting quadratic residues modulo n I'm trying to solve a rather specific problem involving quadratic residues. 
Let $p,q$ be primes $(q > 2)$, such that $p = 2q + 1$, i.e. p is a safe prime.
$\mathbb{Z}^{*}_{p}$ is a multiplicative group modulo $p$, having order $p-1$. 
Next, consider the set $G = \{ x^{2} \bmod p \vert x \in \mathbb{Z}^{*}_{p}  \}$. It can be shown that $G$, the set of quadratic residues modulo $p$, is a subgroup of 
$\mathbb{Z}^{*}_{p}$ having order $q$.
Let's consider two distinct elements $m_{0},m_{1} \in G$, where $m_{0} \neq m_{1}$, and consider the sets $G + m_{0}$ and $G + m_{1}$ where the addition is defined modulo $p$, i.e. $$G + m_{0} = \{ [g + m_{0}]\bmod p \vert g \in G \}$$
$$G + m_{1} = \{ [g + m_{1}]\bmod p \vert g \in G \}$$ 
I am trying to prove that $G + m_{0}$ and $G + m_{1}$ are distinct sets, i.e. their symmetric difference is non-empty. 
Furthermore, if possible, I'm trying to find $m_{0},m_{1}$ that maximizes the cardinality of this symmetric difference, given the group $G$ and looking for an efficient algorithm that does this. I'm not sure if one exists.
The second problem is more of a bonus, which I won't be surprised if it's hard to solve. But the first problem (proving distinctness of the two sets) is pretty true I'm sure, except I'm not sure how to prove it.
 A: To maximise the size of the symmetric difference, you need to minimise the size of
the intersection. A point in the intersection comes from nonzero
$x$, $y\in\Bbb Z_p$
with
$$x^2+m_0=y^2+m_1$$
in $\Bbb Z_p$. More precisely it comes from four such solutions as $(\pm x,pm y)$
all give the same number. So we are counting solutions of
$$x^2-y^2=m_1-m_0$$
with $x$, $y\ne0$. Forgetting about the nonzero-ness condition the equation is
$$(x-y)(x+y)=m_1-m_0$$
and as $m_1-m_1\ne0$ for each nonzero value of $x-y$, there's a unique $x+y$
so there are $p-1$ solutions.
But as $p\equiv3\pmod 4$, precisely one of $\pm(m_1-m_0)$ is a quadratic
residue, and so there are two solutions with one of $x$, $y$ zero. So there
are $\frac14(p-3)$ elements in $(G+m_0)\cap(G+m_1)$ no matter what $m_0$
and $m_1$ are. Thus the symmetric difference has size $p-1-\frac12(p-3)=
\frac12(p+1)$.
A: The element $r=m_1-m_0\neq 0$ additively generates $\Bbb F_p$ so that $\mathcal T_r : t\mapsto t+r$ defines a permutation of $\Bbb F_p$ with only one cauchy cycle ; namely, the entire finite field $\Bbb F_p$ in some order. 
Therefore, if $G = G + r$, i.e. $\mathcal T_r[G] = G$, then $G$ would have to contain a $\mathcal T_r$ orbit. But there is only one such orbit. This implies $\Bbb F_p\subset G$ and thus $p\leq|G| = \frac{p-1}{2}$ which is false.
$$G = G + r \implies \Bbb F_p\subset G\implies p\leq|G| = \frac{p-1}{2}$$
Therefore, $G\neq G+r$ and thus $G+m_0\neq G+m_1$.
The same argument holds for any distinct $m_0, m_1$ regardless of residuacity.
