Some combinations of quadratic residues

Question

Suppose $x\in\{a,b\}$ solve $x^2=m\bmod q$ and $y\in\{c,d\}$ solve $y^2=n\bmod q$ then when do all combinations of $xy\bmod q$ have same least non-negative residue?

Supposing we have $w\in\{e,f\}$ solve $w^2=m\bmod p$ and $z\in\{g,h\}$ solve $z^2=n\bmod p$ when do any combination of $wz\bmod p$ agree with any combination of $xy\bmod q$ at the least non-negative residue?

Answer 1

Okay so this is going to be a bit long winded but it'll have plenty of goodies for you to go through,

Problem statement: find conditions on $m,n,q$ such that solutions to $x^2 =m \mod q, y^2 = n \mod q$, $\lbrace a,b \rbrace$ and $\lbrace c,d \rbrace$ respectively have the property that $ac \equiv ad \equiv bc \equiv bd \mod q$

We will answer this in two phases:

Phase 1: $ac \equiv ad \mod q$

Case 1: $c \equiv d$

then it trivially follows that $ac \equiv ad$, observe that the only times that $c \equiv d$ are when $d \equiv q - c \mod q$ (because $c^2 = (q-c)^2 = n \mod q \forall \ c$) , that of course tells us that $2c \equiv q \ (\text{and likewise} \ 2d \equiv q) $ This is only meaningful when $q$ is even but not divisible by 4 (otherwise you get more than 1 solution) so for $q = 4k+2$ and $n = (k+1)^2$ we have that $ac \equiv ad$

Case 2: $c \not\equiv d$

Then it must be the case that $a$ is a zero divisor (no unit element is going to be able to multiply TWO Different things and get the same answer). Let $e$ be the smallest residue greater than 0 such that $ae = 0$. Then it follows that $d = c + re, r \in \lbrace 0,1 ... a-1 \rbrace$ (you can algebraically verify this). We can then condition that $q$ is not prime and that $c^2 \equiv (c+re)^2 \equiv n$ (now we follow the stringent two solution rule) $c + re \equiv q - c \rightarrow 2c \equiv re \rightarrow c \equiv \frac{1}{2}re$. So again $q$ is going to have to be even, since a zero-divisor of $q$ (re) is even. This yields $n = 9u^2$, $q = 2uk$, (2u) is the zero divisor. From here we deduce $a = hk, h \in \lbrace 0 ... 2u-1 \rbrace$

Now it's easy to see that $bc = bd$ yields the same conditions (with a swapped out by b) so we are ready to tackle the general thing:

Phase II: $ac \equiv ad \equiv bc \equiv bd$

Case 1: $c \equiv d$

We observe $a \equiv b$ yields the condition that $m=n=(k+1)^2, q =4k+2$.

If $ a \not\equiv b$ from our top case we have that: $q =4k+2, n = (k+1)^2$, now suppose we were conditioning on $c$ with $a=b$, then we yield that $m = 9u^2$, $q = 2uj$, $c=hj, h \in \lbrace 0 ... 2u-1\rbrace$. Recalling that $c = \frac{q}{2}$ this concludes that $c = uj$, so our full set of constraints is that: $$ \begin{matrix} q= 2uj \\ n = (\frac{uj+1}{2})^2 \\ m = 9u^2 \end{matrix} $$ Case 2: $c \not\equiv d$ We recalled that $a = hk, h \in \lbrace 0... 2u-1 \rbrace$ where $q = 2uk$. So now we have that $b = h_2k$ and $h^2 = h_2^2$ tell us that $b = -hk$.

that wraps up our conditions.