0
$\begingroup$

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 :)

$\endgroup$
  • $\begingroup$ 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$.) $\endgroup$ – dan_fulea Jun 22 at 3:48
  • $\begingroup$ For example $37^{18}-1$ is divisible by $28728.$ $\endgroup$ – Michael Rozenberg Jun 22 at 3:54
  • 1
    $\begingroup$ 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. $\endgroup$ – saulspatz Jun 22 at 4:04
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.