Are Quadratic residues modulo $n \equiv 1 \bmod 4$ symmetric about $n \over 2$

48 Views Asked by At

If $p \equiv 1 \bmod 4$ is a prime, then the quadratic residues modulo $p$ are symmetric about $\frac p 2$. i.e., $a$ is a QR iff $p-a$ is a QR. Does this property carryover to composite modulus $n = p_1 p_2 \cdots p_k$ where $p_i \equiv 1 \bmod 4$?

Example:

$p = 5$: QRs are $1, 4$ and they are symmetric about $\frac {5} 2$.

$q = 13$: QRs are $1, 3, 4, 9, 10, 12$ and they are symmetric about $\frac {13} 2$.

$n = 5 \times 13 = 65$: QRs are $1, 4, 9, 10, 14, 16, 25, 26, 29, 30, 35, 36, 39, 40, 49, 51, 55, 56, 61, 64$ and they seem to be symmetric about $\frac {65} 2$.

Does this hold for all composite $n \equiv 1 \bmod 4$ where each prime factor is congruent to $1 \bmod 4$?

1

There are 1 best solutions below

0
On BEST ANSWER

$\DeclareMathOperator\ord{ord}$Yes, the desired symmetry holds. For each prime factor $p$ of $n$, since $p \equiv 1 \pmod 4$ by assumption, there is a square root $i_p$ of $-1$ modulo $p$. Since $p$ is odd, by Hensel's lemma, we can lift $i_p$ to a square root $i_{p^{\ord_p(n)}}$ of $-1$ modulo $p^{\ord_p(n)}$. By the Chinese remainder theorem, there is an integer $i_n$ such that $i_n \equiv i_{p^{\ord_p(n)}} \pmod{p^{\ord_p(n)}}$, and hence $i_n^2 \equiv -1 \pmod{p^{\ord_p(n)}}$, for all prime factors $p$ of $n$; so $i_n^2 \equiv -1 \pmod n$. Thus $x^2 \mapsto i_n^2 x^2 = -x^2$ is a reflection of the non-$0$ quadratic residues modulo $n$ about $n/2$.