- #1

- 11

- 0

**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