Number of quadratic residues mod N>1

[THSMathWhiz]

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 $x\in(\mathbb{Z}/N)^\times$ satisfies $x\equiv q^2\bmod N$ for some $q\in(\mathbb{Z}/N)^\times$, then $x$ is a quadratic residue mod $N$.

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

$$\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}$$

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

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

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

In my opinion, step 3 is the hardest. The cases $n=1,2,3$ 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 $x\equiv a^2\bmod 2^n$. Then there is an integer $q$ such that $x=a^2+2^nq$, so $x\equiv a^2+2^nq\bmod 2^{n+1}$. Since there are only two choices of $q$ that make this congruence unique, it should follow that $\phi_2(2^{n+1})=2\phi_2(2^n)$. This is the inspiration for the formula above.

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

By combining all of these facts, we get the theorized formula for $\phi_2(N)$ given its factorization into prime powers. QED

 

[PCM72]

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?

 

[PCM72]

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 $x\in(\mathbb{Z}/N)^\times$, 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:

$$\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}$$

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

 

[PCM72]

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:

$$\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}$$


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 :