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.

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)$.
