# Short Prime Number Divisibility Question

Question: Calculate all prime numbers $$x$$, where $$x^{18} - 1$$ is divisible by $$28728$$

Apparently, the answer is all prime numbers except 2, 3, 7, and 19. I did some prime factorisation and found that 28728 = $$2^3, 3^3, 7, 19$$ and spotted that the numbers that x cannot be with it. However, I still don't know why and how to prove that the answer can be all prime numbers except 2, 3, 7, and 19.

Any help would be extremely appreciated :)

• Fermats theorem that really fits in the margin guarantees that $x^{p-1}-1$ is divisible by $p$ iff $x$ is prime to $p$. Apply this for $p$ among the numbers above. (And also note $x^{18}-1$ is divisible by $x^d-1$, where $d$ divides $18$.) – dan_fulea Jun 22 at 3:48
• For example $37^{18}-1$ is divisible by $28728.$ – Michael Rozenberg Jun 22 at 3:54
• Consider $x^{18}\equiv 1\pmod{m}$ for $m=8,9,7,19$. By the Chinese remainder theorem, a simultaneous solution to all of them solves the original problem. Fermat's little theorem, and Euler's generalization dispose of all $4$ cases. – saulspatz Jun 22 at 4:04

The Carmichael function $$\lambda(n)$$ gives the smallest exponent $$k$$, for which $$x^k\equiv 1\mod n$$ holds for all $$x$$ coprime to $$n$$.
Because of $$\lambda(28728)=18$$ , the congruence $$x^{18}\equiv 1\mod 28728$$ is satisfied for all $$x$$ coprime to $$28728$$ and in particular for all primes except $$2,3,7$$ and $$19$$.