Number of quadratic residues mod N>1

  • #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
 

Answers and Replies

  • #2
3
0
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?
 
  • #3
3
0
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
 
  • #4
3
0
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 :
 

Related Threads on Number of quadratic residues mod N>1

Replies
3
Views
3K
Replies
1
Views
2K
  • Last Post
Replies
2
Views
4K
Replies
7
Views
3K
  • Last Post
Replies
5
Views
6K
  • Last Post
Replies
2
Views
3K
Replies
2
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
2K
Replies
1
Views
3K
Top