4
$\begingroup$

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!

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

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.

$\endgroup$
  • $\begingroup$ But $N(p)=\frac{p-1}{2}$ if $p$ is an odd prime, which seems to contradict the statement... $\endgroup$ – Nishant May 29 '15 at 14:15
  • $\begingroup$ @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. $\endgroup$ – iadvd May 29 '15 at 14:22
  • 1
    $\begingroup$ @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. $\endgroup$ – Asvin May 29 '15 at 14:24
  • 1
    $\begingroup$ @iadvd I have added an example. Try counting with p = 5, n = 10 if you wish. $\endgroup$ – Asvin May 29 '15 at 14:26
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ thank you, easy to follow answer for my level!! $\endgroup$ – iadvd May 30 '15 at 0:23
  • $\begingroup$ 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 $\endgroup$ – iadvd Jun 1 '15 at 1:13
  • 1
    $\begingroup$ Yes, which is what was said in Asvin's answer. It is just a consequence of the CRT. $\endgroup$ – fretty Jun 1 '15 at 10:11
  • 1
    $\begingroup$ 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,...$). $\endgroup$ – fretty Jun 1 '15 at 10:18
  • $\begingroup$ 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. :) $\endgroup$ – iadvd Jun 2 '15 at 0:07
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.