Determine the number of cubic residues modulo a given squarefree number n.
I was given the hint:
An integer coprime to n is a cubic residue if $a = u^3$(mod n) for some u.Start from prime factorization of n, count the solutions of $x^3 ≡ 1$(mod p), and then use Chinese Remainder Theorem
Best Answer
As it's provided in the link, we have:
Now given an odd number not divisible by $3$ $n=\prod_{i=1}^k p_i$, If the congruence $x^3 \equiv a \mod n$ has a solution, that solution is necessarily a solution to each of the prime power congruences $x^3 \equiv a \mod p_i$. Conversely, if you find solutions to each of the prime power congruences, you can use the Chinese Remainder Theorem to produce a unique solution to the original problem. finally the number of total solutions is: $$\prod_{p_i\equiv 1\mod 3} \left(\frac{p_i-1}{3}\right)\prod_{p_i\equiv 2\mod 3}({p_i-1})$$.
Here we did not consider the cases $p=2,3$ it's your turn to handle this two cases.
Edit : Assume that we are given a cube mod $n$ these means $a\equiv x^3\mod n$ then for any prime $p_i$ there exists elments $ x\equiv x_i\mod p_i$ and $a\equiv a_i\mod p_i$ such that $x_i^3=a\mod p_i$ then $a$ is cube modulo any prime $p_i$ .
Now assume that we are given congruences of type $x_i^3\equiv a_i\mod p_i$ for any prime $p_i$ then using Chinese reminder theorem there exists a unique element modulo $n=p_1\cdots p_n$ such that $x\equiv x_i\mod p_i$ for each $i$ and a unique element $a$ such that $a\equiv a_i\mod p_i$ for each $i$ hence $a$ is cube modulo $n$.
Now we have proven that every time we choose a tuple $(a_1,\cdots,a_n)$ of cubes modulo $p_i$ we obtain a cube $a$ modulo $n$ and this injectively hence the number of cubes modulo $n$ is the number of tuples and we are done.