Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number of quadratic residues mod N>1

  1. May 8, 2013 #1
    Any comments or feedback on this theorem and proof are appreciated, including improvements and past publications. Specifically, I'd like to know if someone else has come up with a formula for counting the number of invertible squares modulo N.

    Definition. If [itex]x\in(\mathbb{Z}/N)^\times[/itex] satisfies [itex]x\equiv q^2\bmod N[/itex] for some [itex]q\in(\mathbb{Z}/N)^\times[/itex], then [itex]x[/itex] is a quadratic residue mod [itex]N[/itex].

    Theorem. Suppose [itex]N\in\mathbb{Z}[/itex] has the prime factorization [itex]2^np_1^{l_1}p_2^{l_2}\cdots p_k^{l_k}[/itex], where the [itex]p_i[/itex]s are distinct odd primes. Then the number of quadratic residues mod [itex]N[/itex] is

    [tex]
    \phi_2(N)=\begin{cases}\frac{N}{2^k}\prod_{i=1}^k\left(1-\frac{1}{p_i}\right),&n<4,\\\frac{N}{2^{k-n+3}}\prod_{i=1}^k\left(1-\frac{1}{p_i}\right),&n\geq4.\end{cases}
    [/tex]

    The proof of this requires four steps.
    1) [itex]\phi_2(p)=\frac{p-1}{2}[/itex] for any odd prime [itex]p[/itex].
    2) [itex]\phi_2(p^k)=\frac{p-1}{2}p^{k-1}[/itex]
    3) [itex]\phi_2(2^n)=\begin{cases}1,&n<4,\\2^{n-3},&n\geq4.\end{cases}[/itex]
    4) If [itex](a,b)=1[/itex], then [itex]\phi_2(ab)=\phi_2(a)\cdot\phi_2(b)[/itex].

    The proof of step 1 is easy. Represent [itex](\mathbb{Z}/p)^\times[/itex] as [itex]\{-\frac{p-1}{2},\dots,-2,-1,1,2,\dots,\frac{p-1}{2}\}[/itex]. Observe that this is a complete representative set containing exactly [itex]\phi(p)=p-1[/itex] elements. Square each of these elements and you get a perfectly symmetric set since the minus signs cancel. Thus there are at most [itex]\frac{p-1}{2}[/itex] residues mod [itex]p[/itex]. Since [itex]x^2\equiv1\bmod p\Longleftrightarrow x\equiv\pm1\bmod p[/itex], the homomorphism [itex]\varphi:(\mathbb{Z}/p)^\times\rightarrow(\mathbb{Z}/p)^\times[/itex] has kernel [itex]\{\pm1\bmod p\}[/itex], so the image of [itex]\varphi[/itex] has index 2 in [itex](\mathbb{Z}/p)^\times[/itex]. Thus [itex]\phi_2(p)=\frac{p-1}{2}[/itex] for any odd prime [itex]p[/itex].

    Step 2 is a little more difficult. Suppose [itex]x\equiv a^2\bmod p[/itex] for some odd prime [itex]p[/itex] and [itex]a\not\equiv0\bmod p[/itex]. Then there is an integer [itex]q[/itex] such that [itex]x=a^2+qp[/itex], so [itex]x\equiv a^2+qp\bmod p^k[/itex]. Since there are [itex]p^{k-1}[/itex] choices for [itex]q[/itex] that make the congruence unique, it should follow that [itex]\phi_2(p^k)=p^{k-1}\phi_2(p)=\frac{p-1}{2}p^{k-1}[/itex].

    In my opinion, step 3 is the hardest. The cases [itex]n=1,2,3[/itex] are easy to observe since only odd squares are quadratic residues modulo an even integer, and there is only one such square less than 8. For higher powers, suppose [itex]x\equiv a^2\bmod 2^n[/itex]. Then there is an integer [itex]q[/itex] such that [itex]x=a^2+2^nq[/itex], so [itex]x\equiv a^2+2^nq\bmod 2^{n+1}[/itex]. Since there are only two choices of [itex]q[/itex] that make this congruence unique, it should follow that [itex]\phi_2(2^{n+1})=2\phi_2(2^n)[/itex]. This is the inspiration for the formula above.

    Finally, step 4 is the most critical and requires the Chinese Remainder Theorem. If [itex]x[/itex] is a residue mod [itex]a[/itex] and mod [itex]b[/itex] with [itex](a,b)=1[/itex], then there is a unique solution for [itex]x\bmod ab[/itex]. The number of possible solutions comes from the number of ordered pairs of residues from [itex](\mathbb{Z}/a)^\times\times(\mathbb{Z}/b)^\times[/itex], which comes out to [itex]\phi_2(a)\phi_2(b)[/itex], each of which is a residue mod [itex]ab[/itex]: if [itex]z\equiv r\bmod a\equiv s\bmod b[/itex], set [itex]x\equiv r^2\bmod a\equiv s^2\bmod b[/itex]. By the Chinese Remainder Theorem, [itex]x\equiv z^2(ca+db)[/itex] where [itex]ca+db=1[/itex]. Thus we are guaranteed at least [itex]\phi_2(a)\phi_2(b)[/itex] quadratic residues mod [itex]ab[/itex]. Now suppose [itex]y[/itex] is a residue mod [itex]ab[/itex]. Then the Chinese Remainder Theorem allows us to surmise that [itex]y[/itex] is a residue bod mod [itex]a[/itex] and mod [itex]b[/itex]. Thus we have no more than [itex]\phi_2(a)\phi_2(b)[/itex] quadratic residues mod [itex]ab[/itex]. We conclude that [itex]\phi_2(ab)=\phi_2(a)\phi_2(b)[/itex]

    By combining all of these facts, we get the theorized formula for [itex]\phi_2(N)[/itex] given its factorization into prime powers. QED
     
  2. jcsd
  3. Sep 10, 2014 #2
    Hi. I've tested your formula with Maple and it doesn't work:

    phi2true:= N-> nops({seq(i^2 mod N,i=1..N-1)}) :
    factorset2:= N-> selectremove(x->x[1]=2,ifactors(N)[2]) :
    factorset2(2^3*7^2*11^2);
    [[2, 3]], [[7, 2], [11, 2]]


    phi2false:= proc(N) local f,n,p,k :
    f:= factorset2(N) :
    n:= `if`(f[1]=[],0,f[1,1,2]) :
    p:= map(x->x[1],f[2]) :
    k:= nops(p) :
    return N/2^`if`(n<4,k,k-n+3)*mul(1-1/p,i=1..k)

    end proc :

    phi2true(2^3*7^2*11^2);
    3696
    phi2false(2^3*7^2*11^2);
    9240
    phi2true(2^4*11^3*13^2);
    193076
    phi2false(2^4*11^3*13^2);
    1510080

    May you give me some numerical example and/or tell me if my Maple algorithm is wrong?
     
  4. Sep 12, 2014 #3
    Hi. I hope you are still interested though I had wrongly understood that you meant the number of "all" quadratic residues modulo n, i.e. the squares mod N, while you wrote "invertible squares modulo N", writing also [itex]x\in(\mathbb{Z}/N)^\times[/itex], and then you meant the quadratic residues such that are relatively prime to N: a definition of quadratic residue used by Stangl in 1996 and apparently well used today. Even MathWorld warns about this misunderstanding: http://mathworld.wolfram.com/QuadraticResidue.html .
    So I must to correct my previous Maple line I used to test your formula:

    phi2true:= N-> nops(select(x->igcd(x,N)=1,{seq(i^2 mod N,i=1..N-1)})) :

    However there is a good news too: your formula would work if I change it a little bit. So I think there is a little mistake in your formula and I take the liberty to fix it:

    [tex]\phi_2(N)=\begin{cases}\frac{N}{2^{n+2}}\prod_{i=1}^k\left(1-\frac{1}{p_i}\right),&n<4,\\\frac{N}{2^5}\prod_{i=1}^k\left(1-\frac{1}{p_i}\right),&n\geq4.\end{cases}[/tex]

    In particular, I've changed the exponents of 2.
    You can see that now your formula is fully working in Maple:

    phi2:= proc(N) local f,n,p,k :

    f:= factorset2(N) :
    n:= `if`(f[1]=[],0,f[1,1,2]) :
    p:= map(x->x[1],f[2]) :
    k:= nops(p) :
    return N/2^`if`(n<4,n+2,5)*mul(1-1/p,i=1..k)


    end proc :

    phi2true(2^3*7^2*11^2);
    1155
    phi2(2^3*7^2*11^2);
    1155
    phi2true(2^4*11^3*13^2);
    94380
    phi2(2^4*11^3*13^2);
    94380
     
  5. Sep 13, 2014 #4
    UPDATE:
    Sorry, yesteday I made another mistake: the formula would work only for k=2 (i.e. as in the samples I used).
    This is the correct formula:

    [tex]\phi_2(N)=\begin{cases}\frac{N}{2^{n+k}}\prod_{i=1}^k\left(1-\frac{1}{p_i}\right),&n<4,\\\frac{N}{2^{3+k}}\prod_{i=1}^k\left(1-\frac{1}{p_i}\right),&n\geq4.\end{cases}[/tex]


    This the correct full Maple procedure:

    factorset2:= N-> selectremove(x->x[1]=2,ifactors(N)[2]) :
    phi2false:= proc(N) local f,n,p,k :
    f:= factorset2(N) :
    n:= `if`(f[1]=[],0,f[1,1,2]) :
    p:= map(x->x[1],f[2]) :
    k:= nops(p) :
    return N/2^`if`(n<4,n+k,3+k)*mul(1-1/p,i=1..k)

    end proc :


    And these are two Maple lines to test an infinite loop of random integers until 1 000 000

    phi2true:= N-> nops(select(x->igcd(x,N)=1,{seq(i^2 mod N,i=1..N-1)})) :
    do sample:= rand(10^6)() : if phi2true(sample)<>phi2(sample) then print(sample) end if end do :
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Number of quadratic residues mod N>1
Loading...