- #1
THSMathWhiz
- 10
- 0
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_is are distinct odd primes. Then the number of quadratic residues mod N is
<br /> \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}<br />
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
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_is are distinct odd primes. Then the number of quadratic residues mod N is
<br /> \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}<br />
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