0
$\begingroup$

In a numerical experiment I notice for sum moduli $N$ there are much less than $N/2$ perfect squares. I had chosen a large number, the simplest example is $N=8$.

Using the Chinese Remainder Theorem (as here) and prime factorization one can solve

$$x^2 \equiv a \mod pq $$

in terms of two equations $x^2 \equiv a \mod p $ and $x^2 \equiv a \mod q $.

If $a$ is a quadratic residue with respect to all of these moduli you can get a solution or you get none at all.


The number of quadratic residues mod $n$ is OEIS sequence A000224:

a(n) = 1, 2, 2, 2, 3, 4, 4, 3, 4, 6, 6, 4, 7, 8, 6, 4, 9, 8, 10, 6

This function is multiplicative and there is a closed formula for each prime power modulus:

$$ a(p^e) = \begin{cases} \big[\frac{1}{6} p^e\big] & \text{ if } p=2 \\ \big[\frac{1}{2(p+1)} p^{e+1}\big] & \text{ if } p\neq2 \end{cases} $$

How to prove this result? Why does the floor function play a role here?

$\endgroup$
1
$\begingroup$

The "floor" is actually hiding what is actually happening. You should see Stangl's paper for the proof (MAA link) (PDF link).

The original formula is (for $n \ge 3$):

$$ s(p^n) = \begin{cases} \frac{p^{n+1}+p+2}{2p + 2} & p\neq 2 \text{ and $n$ even} \\ \frac{p^{n+1}+2p+1}{2p + 2} & p\neq 2 \text{ and $n$ odd} \\ \frac{2^{n-1}+4}{3} & p = 2 \text{ and $n$ even} \\ \frac{2^{n-1}+5}{3} & p = 2 \text{ and $n$ odd} \end{cases}$$

which is proven using the recurrence formula:

$$ s(p^n) = q(p^n) + s(p^{n-2}) $$

where $s(x)$ is the number of squares and $q(x)$ is the number of quadratic residues (only units).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.