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

• I'm not sure I understand the last paragraph. Can you elaborate? Apr 25, 2019 at 16:39

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.