How many elements in the natural system of representative of $5400$ are squares $\mod 5400$?

Question

I was working on the problem: Consider the set $S=\{0,1,...,5399\}$ be the natural system of representatives $\mod5400$. How many elements of $S$ are squares $\mod 5400$. But shouldn't the answer just be the number of squares between $0$ an $5399$? Am I oversimplifying the problem?

Answer 1

For a hint on the number of quadratic residues, note that if $a$ is a quadratic residue mod $5400$, then $x^2 \equiv a \mod 5400$ for some $x$. Consequently, $a$ is also a square mod $l$ for any divisor $l$ of $5400$. In particular, this applies for $l = 8,25,27$, which are the prime powers in the decomposition of $5400$.

However, the converse is also true. More precisely, $a$ is a quadratic residue mod $5400$ if and only if it is a quadratic residue modulo the numbers $8,25,27$. That is , every quadratic residue mod $5400$ arises uniquely from a triple of quadratic residues mod $8,25,27$. So the answer is the product of the quadratic residues mod $8,25,27$.(This is a corollary of the Chinese remainder theorem)

Therefore, to compute the answer, you can do the following :

• The number of quadratic residues mod $8$ can be found by hand : it is $3$, namely $0,1,4$.

• Find the number of quadratic residues mod $3$ and $5$(respectively $2$ and $3$).

• To find the number of quadratic residues mod $25$, we use the fact(from Hensel lemma) that $a$ is quadratic modulo $p$ implies it is a quadratic residue mod $p^k$, if $p \nmid a$ and $p \neq 2$. Therefore, of the numbers $0,1,-1$ which are quadratic residues mod $5$, the numbers $1,-1$ provide $5$ each, or in total $10$ residues mod $25$ (for example, $1$ provides $1,6,11,16,21$ mod $25$, and similarly you can see what $-1$ provides). Note that $0$ does not lift, since $25a + 5b$ is a perfect square implies $5 | b$, or that $5b$ is a multiple of $25$. Thus, counting just the $0$ we get $11$ in total.

• To find the number of quadratic residues mod $27$, we see that $1$ which the only non-zero quadratic residue mod $3$, contributes $9$ residues mod $27$. Certainly $0$ counts. Only leftovers are multiples of $3$ now, since $2$ is a non-residue of $3$. Of these, we see that if $x^2 \equiv 3a \mod 27$, then $27 + 3a$ is a multiple of $3$, therefore $9$. So $3 | a$. This gives only $9$ and $18$ as possibilities. Of these, $9$ is a square, so therefore a square mod $27$. For the other, if $x ^ 2 = 27a+18$, then $\frac{x^2}{9} = 3a+2$ is a perfect square, giving a contradiction mod $3$. Consequently, $0$ and $9$ are the only other quadratic residues, giving $11$ in total, again.

• Now multiply these : $3 \times 11 \times 11 = 363$.