16
$\begingroup$

Let $p$ be a prime number such that $p \equiv 1 \pmod 4$. Prove that $\frac{p^p-1}{p-1}$ is not prime.

We can rewrite $\frac{p^p-1}{p-1}$ as $$\dfrac{p^p-1}{p-1} = 1+p+p^2+\cdots+p^{p-1},$$but how do we show this is not prime?

$\endgroup$
  • 2
    $\begingroup$ Would be much easier if it were $\frac{p^{p-1}-1}{p-1}$. Or $\frac{p^{p+k}-1}{p-1}$ for any odd $k$, really. $\endgroup$ – Gabriel Burns Nov 3 '16 at 14:02
  • 2
    $\begingroup$ What have you tried? I factored the numbers with $p=5,13,17$ and didn't find any factors that were obviously related to $p$ $\endgroup$ – Ross Millikan Nov 3 '16 at 14:05
  • 1
    $\begingroup$ Possibly related: math.stackexchange.com/questions/223847/… $\endgroup$ – Watson Nov 3 '16 at 14:23
  • 1
    $\begingroup$ @RossMillikan if $f(p) = \frac{p^p - 1}{p - 1}$, then $5\times 2 + 1 \mid f(5)$ and $13 \times 4 + 1 \mid f(13)$ and $17 \times 644 + 1 \mid f(17)$ ... the key seems to be to look at the problem in terms of $\pmod {p + 1}$, and it might help to keep in mind the the sum $\sum_{k = 1}^p p^k \equiv \sum_{k = 1}^p k \pmod{p + 1}$ because modular exponents form a bijection. $\endgroup$ – DanielV Nov 3 '16 at 14:26
  • 3
    $\begingroup$ @user Where do you get this stuff? $\endgroup$ – Will Jagy Nov 3 '16 at 20:33
2
$\begingroup$

We may notice that $\frac{p^p-1}{p-1}=\Phi_p(p)$, where $\Phi_p$ is the $p$-th cyclotomic polynomial. If we assume that for some prime $q$ we have $\Phi_p(x)\equiv 0\pmod{q}$, then $x$ has order $p$ in $\mathbb{Z}/(q\mathbb{Z})^*$, hence $p\mid(q-1)$, or $q\equiv 1\pmod{p}$, by Lagrange's theorem. Additionally, the constraint $p\equiv 1\pmod{4}$ ensures that $\Phi_p(p)$ has a Aurifeuillean factorization.

$\endgroup$
  • $\begingroup$ Does this solve the question? $\endgroup$ – user19405892 Nov 3 '16 at 18:52
  • $\begingroup$ @user19405892: I guess so, since a Aurifeuillean factorization ensures that $\Phi_p(p)$ cannot be prime. $\endgroup$ – Jack D'Aurizio Nov 3 '16 at 18:53
  • $\begingroup$ For short, the fact that $p$ splits in $\mathbb{Z}[i]$ implies that $\Phi_p(p)$ splits over $\mathbb{Z}$. $\endgroup$ – Jack D'Aurizio Nov 3 '16 at 18:54
  • 1
    $\begingroup$ Where can I find a reference about proofs of which cyclotomic polynomials have an Aurifeuillean factorization ? $\endgroup$ – user456828 Oct 17 '17 at 15:14
  • 1
    $\begingroup$ @misao I found Paul Garrett's notes on Aurifeuillean stuff useful. Note, Paul Garrett also contributes here occasionally. $\endgroup$ – Jyrki Lahtonen Oct 21 '17 at 5:41

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.