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

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 gmpy2 import is_prime

def list_qrmn(n):
lqrmn = []
for i in range (1,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!

• What do you mean by "the length of the quadratic residues"? Do you just mean, the number of quadratic residues? – Gerry Myerson May 29 '15 at 13:19
• @GerryMyerson yes, the number of quadratic residues, I wanted to mean the lenght of the set of quadratic residues... – iadvd May 29 '15 at 13:21
• Then let me suggest you edit the quesiton so it says that. – Gerry Myerson May 29 '15 at 13:22
• @GerryMyerson thank you, done! – iadvd May 29 '15 at 13:27

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.

• But $N(p)=\frac{p-1}{2}$ if $p$ is an odd prime, which seems to contradict the statement... – Nishant May 29 '15 at 14:15
• @Asvin thank you for taking time to answer, please may I ask you for an specific example of n,m for this generalization? I get lost in your nice theoretical explanation. Probably with a very specific example I would see it clear. – iadvd May 29 '15 at 14:22
• @Nishant $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. – Asvin May 29 '15 at 14:24
• @iadvd I have added an example. Try counting with p = 5, n = 10 if you wish. – Asvin May 29 '15 at 14:26

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.

• thank you, easy to follow answer for my level!! – iadvd May 30 '15 at 0:23
• I was reviewing your nice answer, may I ask you something very simple? About your phrase, "counting squares mod mn is the same as counting pairs of squares mod m and mod n separately... whenever m,n are coprime". If I understood, then does that mean that "counting squares mod mn" is a multiplicative function? (like Totient function, Mobius, etc.) Thank you! en.wikipedia.org/wiki/Multiplicative_function – iadvd Jun 1 '15 at 1:13
• Yes, which is what was said in Asvin's answer. It is just a consequence of the CRT. – fretty Jun 1 '15 at 10:11
• Have you tried the same for $4p$? It should still work since there are exactly two squares mod $4$. However the result will not work for $kp$ if $k>4$ since there are definitely more than $2$ squares mod $k$ ($0,1,4,...$). – fretty Jun 1 '15 at 10:18
• yes, $4p$ is also working. When I did the test I did not know why the results were ok up to a certain value of $kp$. Another interesting point is that certain primes are able of "hitting" quadratic residue mod n lists of size a prime number over $4p$, for instance $p=11$ is able to "hit" primes up to $k=9$, $9*11=99$, so it is also interesting to know which one of them are able to hit primes up to for instance $p\cdot(p-1)$, if any. But that is another history. :) – iadvd Jun 2 '15 at 0:07

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