2
$\begingroup$

I would just like to get some help in proving that the number of QRs for $n = p_1^{i}p_2^{j}p_3^k...p_\alpha^i$ is $\frac{\phi(n)}{2^\alpha} $.

Intuitively, I understand that each prime $p^i$ 'brings' $\frac{\phi(p^i)}{2} $ QRs to $n$ and obviously multiplying each of these together gives $\frac{\phi(n)}{2^\alpha} $.

I know this question is similar to:

On the number of quadratic residues $\pmod{pq}$ where$p$ and $q$ are odd primes.

But could someone help me with how I would make my intuition a more formal generalised proof?

Many thanks!

$\endgroup$
1
  • 1
    $\begingroup$ It is usually more useful to write $p_1^{m_1}p_2^{m_2}\ldots$. $\endgroup$
    – Pedro
    Oct 20, 2013 at 2:43

1 Answer 1

1
$\begingroup$

Here is a heuristic justification that will give you grounds for more formal justification. First of all, it should make sense that there are $\frac{p-1}{2}$ quadratic residues $\pmod{p}$, because the congruence $x^{2} \equiv a \pmod{p}$ should have two solutions: $x$ and $-x$, and there are $p-1$ non-zero residues $\pmod{p}$, so we're just pairing each $x$ with a $-x$ to leave $\frac{p-1}{2}$ solutions. Now consider the congruence $x^{2} \equiv a \pmod{n}$, where $n = pq$ and $p$ and $q$ are both odd primes. Remember that $x^{2} \equiv a \pmod{n} \iff x^{2} = a + nk$ for some $k \in \mathbb{Z}$. But remember that since $p \vert n$ and $q \vert n$, so we could get the same $a$ just by dividing $x^2$ by $p$ or $q$.
Well, first of all, it should make sense that there are $\frac{p-1}{2}$ quadratic residues $\pmod{p}$, because the congruence $x^{2} \equiv a \pmod{p}$ should have two solutions: $x$ and $-x$, and there are $p-1$ non-zero elements $\pmod{p}$, so we're just taking half of these. Now consider the congruence $x^{2} \equiv a \pmod{n}$, where $n = pq$ and $p$ and $q$ are both odd primes. Remember that $x^{2} \equiv a \pmod{n} \iff x^{2} = a + nk$ for some $k \in \mathbb{Z}$. But remember that since $p \vert n$ and $q \vert n$, so we could get some of the same $a$ just by dividing $x^2$ by $p$ or $q$. Also note that the set of quadratic residues $\pmod{p}$ is closed under multiplication (because $x^2y^2 = (xy)^2$). So if there are $\frac{p-1}{2}$ residues that we already know will be quadratic $\pmod{n}$ because we know $p \vert n$, it should make sense that we would be able to make more quadratic residues by multiplying each of the $\frac{p-1}{2}$ quadratic residues by the $\frac{q-1}{2}$ quadratic residues as a result of this closure. Because $n$ has only two prime divisors, we know that we can't do this again. So we know that there should then be exactly $\frac{p-1}{2} \cdot \frac{q-1}{2} = \frac{(p-1)(q-1)}{2^2}$ quadratic residues $\pmod{n}$. It should make sense why we can make more or less quadratic residues by this multiplication process which is dependent on the number of prime divisors of $n$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .