How many numbers $x$ less than $30030$ are there such that $30030$ divides $x^3-1$

Question

How would you tackle this problem? I am looking for hints. The things I have observed so far: $30030 = 2\cdot3\cdot5\cdot7\cdot11\cdot13$. So none of these prime numbers can divide $x$. This gets rid of a significant number of candidates but still leaves a merry number of them hanging.

EDIT: I didn't mention it but we are looking for positive solutions.

Answer 1

Here is a start. The Chinese Remainder Theorem tells us that we can deal with each of the primes separately. Let's take some examples:

For the prime $2$ it is obvious that $x$ must be odd.

Modulo the prime $5$ the cubes are $0^3=0, 1^3=1, 2^3=3, 3^3=2, 4^3=4$ so we must have $x\equiv 1 \bmod 5$

Modulo the prime $7$ we find that $1^3=2^3=4^3=1$ so $\frac 37$ of the possibilities work modulo $7$.

See if you can work it out from here before you read on.

Now the difference between $5$ and $7$ is that $7-1=2\times 3$ where $3$ is the power we are interested in. Modulo $7$ we have $x^6-1=0=(x^3-1)(x^3+1)$ (little Fermat) and there are three cube roots of $1$ rather than just the one.

With these clues you should be able to work it out (if in doubt try $70$ instead of $30030$ to start with)