Why is it true for every prime $p>7$ that $p+1$ divides $\prod\limits_{[1,p]}\text{(the quadratic residues modulo $p+1$)}$?

Question

Learning about the quadratic residues mod $n$ (link to Wikipedia), "$qr\ mod\ n$" for short, I made some tests focused on those $qr \in [1,n-1]$ (not including the quadratic residue $0$) and stumbled upon this possible property, :

(1) $\forall p\in\Bbb P$, $p > 7$, $p+1 \mid \prod_{[1,p]} \text{qr modulo $p+1$}$

In other words, it seems that for any prime number $p$ greater that $7$, $p+1$ is a factor of the product of the set of quadratic residues mod $(p+1)$ of the interval $[1,p]$ (I mean, $0$ is not included).

E.g.:

$n=30=p+1=29+1$,

$qr\ mod\ 30=\{0,1,4,6,9,10,15,16,19,21,24,25\}$,

$\prod_{[1,29]} (qr\ mod\ 30) = 1\cdot4\cdot6\cdot9\cdot10\cdot15\cdot16\cdot19\cdot21\cdot24\cdot25=124104960000$,

and $30\mid \prod (qr\ mod\ 30)(=124104960000)$.

This is a very brute-force quick Python test for $[1,2\cdot 10^4]$:

def qrmn():
    from sympy import is_quad_residue
    from gmpy2 import is_prime, mul, mpz

    def list_qrmn(n):
        lqrmn = []
        totprod = mpz(1)
        for i in range (1,n):
            if is_quad_residue(i,n):                    
                lqrmn.append(i)
                totprod = mul(totprod,i)
        return lqrmn, totprod

    for n in range (8,20000):
        if is_prime(n):
            lqrmn, totprod = list_qrmn(n+1)
            if totprod%(n+1)==0:
                print("SUCCESS: " + str(n))
            else:
                print("ERROR: " + str(n))   
qrmn()

So my question is: why does (1) happen? I am sure that it is due to the properties of the quadratic residues, but my theoretical knowledge is very basic so any help is very appreciated.

Thank you!

Answer 1

Let $n=\prod_{1}^{k}p_i^{\alpha_i}$. Assume $k>1$, then one of your quadratic residues is of the form $(p_i^{\alpha_i})^2 + rn$ for each $i$. Therefore the product of all of the quadratic residues contains one factor of the form $\prod_{1}^{k}p_i^{\alpha_i} + \lambda n = n(1 + \lambda)$ which is clearly divisible by $n$.

I will leave the case of $n$ being a prime power to you. Try finding out which prime powers it works for and which ones it does not. Note that it is not really important if $n-1$ is a prime.

Answer 2

Much more seems to be true:

Suppose $n$ is any positive integer. Let $P$ be the product of the quadratic residues modulo $n$ which are not equal to $0$.

(i.e. $P$ is the product of the elements in the set $\{x^2 \mod n : x \in \mathbb{Z}\}\setminus \{0\}$)

Then $n \mid P$ if and only if $n \not\in \mathbb{P}\cup\{x^2 : x \in \mathbb{P}\} \cup \{8, 16, 27\}$ where $\mathbb{P}$ is the set of prime numbers.

We will first deal with the case where $n$ has at least $2$ distinct prime factors:

If $n$ has at least $2$ distinct prime factors, then we can write $n=ab$ where $a$ and $b$ are relatively prime, and neither is equal to $1$.

Then the numbers $(a^2 \mod n)$ and $(b^2 \mod n)$ are two distinct quadratic residues modulo $n$, and neither is equal to $0$. (If $n \mid a^2$, for example, then we would have $b \mid a$, which contradicts that $a$ and $b$ are relatively prime)

The product of these two numbers is congruent to $a^2b^2 \equiv 0 \mod n$, and this product divides $P$, and hence $n \mid P$.

Now suppose that $n$ has only one distinct prime factor. i.e. $n$ is a power of a prime. Let $n = p^k$ where $p$ is prime.

Suppose $k>4$. If $k$ is even, then $p^2$ and $p^{k-2}$ are distinct quadratic residues modulo $n$, and their product is $n$, and so $n \mid P$.

If $k$ is odd, then $p^2$ and $p^{k-1}$ are distinct quadratic residues modulo $n$, and their product is $p^{k+1}$, which is divisible by $n$, and so $n \mid P$.

The only cases that remain are if $n \in \{p, p^2, p^3, p^4\}$.

If $n$ is a prime, then no positive integer less than $n$ is divisible by $n$. Thus none of the quadratic residues modulo $n$ is divisible by $n$, and so their product, $P$, is not divisible by $n$. (Since $n$ is prime)

If $n = p^2$, then for $P$ to be divisible by $n$, one of the quadratic residues modulo $n$ must be divisible by $p$. Suppose $p \mid (x^2 \mod n)$. Then $p \mid x^2 - kp^2$ for some $k$, and so $p \mid x$. But then $x^2 \equiv 0 \mod p^2$, and so $(x^2 \mod n) = 0$. But we are only considering the product of the non-zero residues modulo $n$, and so we again can see that $n$ does not divide $P$.

If $n \in \{p^3, p^4\}$, and $p \geq 5$, then $p^2$ and $4p^2$ are two distinct quadratic residues modulo $n$, and their product is divisible by $n$, and so again $n \mid P$.

The only cases that are left to check are

$n \in \{8, 16, 27, 81\}$, and we can manually verify that the only one of these values of $n$ for which $n \mid P$ is $n = 81$

So the only exceptions to your conjecture are prime numbers, squares of prime numbers, and the numbers $8$, $16$ and $27$.