Modular Cubes, Part 1

For a positive number $n$, define $S(n)$ as the sum of the integers $x$, for which $1 \lt x \lt n$ and$x^3 \equiv 1 \bmod n$.

When $n=91$, there are $8$ possible values for $x$, namely: $9, 16, 22, 29, 53, 74, 79, 81$.
Thus, $S(91)=9+16+22+29+53+74+79+81=363$.

Find $S(13082761331670030)$.

This problem uses advanced concepts in number theory, namely cubic residue and chinese remainder theorem.

Firstly, we know that $13082761331670030 = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 23 \cdot 29 \cdot 31 \cdot 37 \cdot 41$. This prime factor decomposition is important because $\mathbb{Z}/n\mathbb{Z}$ is not necessarily a field, but $\mathbb{Z}/p\mathbb{Z}$ is.

By the Chinese remainder theorem, we can consider this problem independently for each prime powers. If $p$ is the prime, we need to find $x$’s such that $x^3 \equiv 1 \mod p^k$ if $p \neq 3$ and $x^3 \equiv 1 \mod 3^k$ except for $x \equiv 0 \mod 3$ if $p=3$. Since the set of third roots of unity is given by $x^2+x+1=0$ or $x \equiv 1 \mod p^k$.

Hence we need to solve $x^2+x+1 \equiv 0 \mod p^k$ for $x \neq 1$.
When $p\neq 3$, the roots can easily be shown to be $m(p^k)$ and $-m(p^k)-1$ where $2m(p^k)+1$ is a primitive root modulo $p^k$, furthermore $2m(p^k)$ and $2m(p^k)+2$ will also be solutions to $x^3 \equiv 1 \mod p^{k+1}$ leading to solution of the next power so in these cases, $S(p^k)=p^k-1$.
Hence for $p\neq 3$ primes, $S(p)=p-1$.

When $p=3$, except for $x \equiv 0 \mod 3$ it will be $x=3^k$, so $S(3^k)=3^k$.

Therefore, you get $S(13082761331670030) = (2-1)(3)(5-1)(7-1)(11-1)(13-1)(17-1)(19-1)(23-1)(29-1)(31-1)(37-1)(41-1)$.

Therefore, $S(13082761331670030) = 423898950732095600$.

More Answers: