Is there a counterexample? $\forall\ p \gt 3 \in \Bbb P, (number\ of\ Quadratic\ Residues\ mod\ kp)=p\ when\ k\in\{2,3\}$

Question

I have started to learn about the properties of the quadratic residues modulo n (link) and reviewing the list of quadratic residues modulo $n$ $\in [1,n-1]$ I found the following possible property:

(1) $\forall\ p \gt 3\in \Bbb P, \ (number\ of\ Quadratic\ Residues\ mod\ kp)=p\ when\ k\in\{2,3\}$

In other words: (a) if $n$ is $2p$ or $3p$, where $p$ is a prime number greater than $3$, then the total number of the quadratic residues modulo $n$ is exactly the prime number $p$. (b) And every prime number $p$ is the number of quadratic residues modulo $2p$ and $3p$.

E.g.:

$n=22$, the list of quadratic residues is $\{1,3,4,5,9,11,12,14,15,16,20\}$, the total number is $11 \in \Bbb P$ and $22=11*2$.

$n=33$, the list of quadratic residues is $\{1,3,4,9,12,15,16,22,25,27,31\}$, the total number is $11 \in \Bbb P$ and $33=11*3$.

I did a quick Python test initially in the interval $[1,10^4]$, no counterexamples found. Here is the code:

def qrmn():
    from sympy import is_quad_residue
    from gmpy2 import is_prime

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

    tested1 = 0
    tested2 = 0
    for n in range (4,10000,1):
        lqrmn = list_qrmn(n)
        # Test 1
        if is_prime(len(lqrmn)):
            if n==3*len(lqrmn) or n==2*len(lqrmn):
                print("SUCCESS1 " + str(n) + " len " + str(len(lqrmn)) + " div " + str(int(n/len(lqrmn))))
                tested1 = tested1 + 1

        # Test 2
        if n==3*len(lqrmn) or n==2*len(lqrmn):
            if is_prime(len(lqrmn)):
                print("SUCCESS2 " + str(n) + " len " + str(len(lqrmn)) + " div " + str(int(n/len(lqrmn))))
                tested2 = tested2 + 1
            else:
                print("ERROR2 " + str(n) + " len " + str(len(lqrmn)) + " div " + str(int(n/len(lqrmn))))

    if tested1 == tested2:
        print("\nTEST SUCCESS: iif condition is true")
    else:
        print("\nTEST ERROR: iif condition is not true: " + str(tested1) + " " + str(tested2))

qrmn()

I am sure this is due to a well known property of the quadratic residues modulo $n$, but my knowledge is very basic (self learner) and initially, reviewing online, I can not find a property of the quadratic residues to understand if that possible property is true or not.

Please I would like to share with you the following questions:

1. Is (1) a trivial property due to the definition of the quadratic residue modulo n?

2. Is there a counterexample?

Thank you!

Answer 1

More generally, Let $N(n) = \{\textrm{the number of quadratic residues in Z/nZ}\}$.

Then for $n,m$ coprime, $N(nm) = N(n)N(m)$. This will follow from the chinese remainder theorem($Z/mnZ = Z/mZ\times Z/nZ$) and basic group theory. Try working through the details.

Example: For $p$ prime: $N(p) = p+1/2, 0$ is a square. $N(2) = |\{0,1\}| = 2, N(3) = |\{0,1\}| = 2$ . I get $p+1$ since I am including $0$ and the op isn't.

Answer 2

The Chinese Remainder theorem lets us conclude that counting squares mod $mn$ is the same as counting pairs of squares mod $m$ and mod $n$ separately...whenever $m,n$ are coprime.

Note that there are exactly two squares mod $2$ and same mod $3$.

It is also known that modulo an odd prime there are $\frac{p-1}{2} + 1$ squares (including $0 \bmod p$).

So putting this together, when counting squares mod $2p$ or $3p$ and $p>3$ (so is coprime to $2,3$) we should get exactly $2(\frac{p-1}{2}+1) = p+1$ squares.

You seem to be discounting $0 \bmod kp$ as a square, hence why you got exactly $p$ non-zero squares.

Answer 3

Say $N=2p$ then $$\#\{y:x^2\equiv y(\ {\rm{mod}} N)\}$$ is equal (from CRT) $\#\{y:x^2\equiv y(\ {\rm{mod}} p)\}\times 2-1=p$ (we subtract $-1$ since we add the solution $x=0$ twice. We have $\frac{p+1}{2}\times 2$ equations but two of them are the same.). More general if $N=p_1p_2\cdots p_k$ and $p_j$ are distinct odd primes then you get $\frac{1}{2^n}\prod_{i=1}^n(p_i+1)-1.$