A Formula For P(n) = N(n)

The Functions R(n), r(n), P(n), and N(n)

On The Functions R(n), r(n), P(n), and N(n) page we defined the special functions $R$, $r$, $P$, and $N$, and noted that for every $n \in \mathbb{N}$:

• a) $r(n) = 4P(n)$.

• b) $P(n) = N(n)$.

• c) $\displaystyle{R(n) = \sum_{d^2|n} r \left ( \frac{n}{d^2} \right )}$.

We will now come up with a formula to compute $P(n) = N(n)$ explicitly.

Proposition 1: If $x^2 \equiv -1 \pmod m$ has $M$ solutions and $x^2 \equiv -1 \pmod n$ has $N$ solutions and if $(m, n) = 1$ then $x^2 \equiv -1 \pmod {mn}$ has $MN$ solutions.

Proposition 1 tells us that $N$ is a multiplicative function.

• Proof: This follows immediately by The Chinese Remainder Theorem. $\blacksquare$

Proposition 2: The congruence $x^2 \equiv -1 \pmod p$ has: a) $0$ solutions if $p \equiv 3 \pmod 4$. b) $1$ solution if $p = 2$. c) $2$ solutions if $p \equiv 1 \pmod 4$.

• Proof: Recall that the Legendre symbol $\left ( \frac{-1}{p} \right ) = - 1$ if $p \equiv 3 \pmod 4$ and $\left ( \frac{-1}{p} \right ) = 1$ if $p \equiv 1 \pmod 4$, which is (a) and (c). Also $x^2 \equiv -1 \pmod 2$ has only $1$ solution, namely $x = 1$, which is (b). $\blacksquare$

Proposition 3: The congruence $x^2 \equiv -1 \pmod {2^{\alpha}}$ has: a) $0$ solutions if $\alpha \geq 2$. b) $1$ solution if $\alpha = 1$.

• Proof: (b) is exactly the same statement as Proposition 2 (b). For (a), if $\alpha \geq 2$, then $x^2 \equiv -1 \pmod {2^{\alpha}}$ implies that $2^{\alpha} | (x^2 + 1)$. So $x$ must be odd. But $x^2 \equiv 1 \pmod 4$. So $x^2 + 1 \equiv 2 \pmod {2^{\alpha}}$ which implies that $\alpha = 1$. So $x^2 \equiv -1 \pmod {2^{\alpha}}$ has 0 solutions if $\alpha \geq 2$. $\blacksquare$

Proposition 4: The congruence $x^2 \equiv -1 \pmod {p}$ where $p \equiv 3 \pmod 4$ has $0$ solutions, and more generally, $x^2 \equiv -1 \pmod {p^k}$ where $p \equiv 3 \pmod 4$ has $0$ solutions.

• Proof: Since $p \equiv 3 \pmod 4$, $x^2 \equiv -1 \pmod p$ and $x^2 \equiv -1 \pmod {p^k}$ have no solutions by the Legendre symbol $\left ( \frac{-1}{p} \right ) = -1$. $\blacksquare$

Proposition 5: The congruence $x^2 \equiv -1 \pmod p$ where $p \equiv 1 \pmod 4$ has $2$ solutions, and more generally, $x^2 \equiv -1 \pmod {p^k}$ where $p \equiv 1 \pmod 4$ has $2$ solutions.

• Proof: Since $p \equiv 1 \pmod 4$, $x^2 \equiv -1 \pmod p$ has two nonzero solutions, that is $x^2 + 1 \equiv 0 \pmod p$ has two nonzero solutions. Let $f(x) = x^2 + 1$. Then $f'(x) = 2x$. Observe that $f'(x) \equiv 0 \pmod p$ if and only if $x = 0$. Thus $f'(s) \not \equiv 0 \pmod p$ if $x$ is a solution to the congruence. So by Hensel's Lemma, the solutions $s_1$ and $s_2$ of $x^2 \equiv -1 \pmod p$ can be uniquely lifted to solutions of $x^2 \equiv -1 \pmod {p^k}$, and there are two of them. $\blacksquare$

Theorem 6: Let $p$ be a prime and let $k \in \mathbb{Z}$. Then $P(p^k) = N(p^k) = \left\{\begin{matrix} 0 & \mathrm{if} \: p = 2^{\alpha}, \: \alpha \geq 2 \: \mathrm{or} \: p \equiv 3 \pmod 4\\ 1 & \mathrm{if} \: p = 2 \\ 2 & \mathrm{if} \: p \equiv 1 \pmod 4 \end{matrix}\right.$. More generally, if $n \in \mathbb{N}$ then $N(n) = P(n) = \left\{\begin{matrix} 0 & \mathrm{if \: there \: is \: a \: prime \:} p \: \mathrm{such \: that \:} p|n \: \mathrm{and} \: p \equiv 3 \pmod 4 \\ 2^k & \mathrm{otherwise, \: where \:} k \: \mathrm{is \: the \: number \: of \: primes \:} p \: \mathrm{such \: that \:} p \equiv 1 \pmod 4 \end{matrix}\right.$.

• Proof: This follows immediately by propositions 1-6. $\blacksquare$

Corollary 7: Let $n \in \mathbb{N}$. Then $r(n) = \left\{\begin{matrix} 0 & \mathrm{if \: there \: is \: a \: prime \:} p \: \mathrm{such \: that \:} p|n \: \mathrm{and} \: p \equiv 3 \pmod 4 \\ 2^{k+2} & \mathrm{otherwise, \: where \:} k \: \mathrm{is \: the \: number \: of \: primes \:} p \: \mathrm{such \: that \:} p \equiv 1 \pmod 4 \end{matrix}\right.$

• Proof: This follows immediately from the fact that $r(n) = 4P(n)$. $\blacksquare$