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.(adsbygoogle = window.adsbygoogle || []).push({});

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 aquadratic residuemod [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

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Number of quadratic residues mod N>1

**Physics Forums | Science Articles, Homework Help, Discussion**