Prove that $n=\dfrac{5^{125}-1}{5^{25}-1}$ is a composite number

My attempt,

Let $x=5^{25}$, so that $5^{125}-1=x^5-1=(x-1)(x^4+x^3+x^2+x+1)$



I'm stuck at this point and don't know how to continue anymore. Hope someone can provide a detailed solution. Thanks a lot.

  • 7
    $\begingroup$ Hint: Note that $5x=5^{26}=(5^{13})^2$. $\endgroup$ – Colescu Jun 8 '17 at 14:42
  • 6
    $\begingroup$ You're on the right Aurifeuillean track. Compare with this $\endgroup$ – Jyrki Lahtonen Jun 8 '17 at 14:50
  • 2
    $\begingroup$ gross. it has 5 HUGE prime factors $\endgroup$ – Saketh Malyala Jun 8 '17 at 15:06
  • $\begingroup$ @JaideepKhare Are you sure $9x^2+2x^2-10x^2=x^2$? $\endgroup$ – kingW3 Jun 8 '17 at 15:50
  • $\begingroup$ en.wikipedia.org/wiki/Aurifeuillean_factorization , see row $b=5$. $\endgroup$ – Jack D'Aurizio Jun 8 '17 at 16:52

The polynomial $\Phi_5(x)=x^4+x^3+x^2+x+1$ fulfills an interesting identity.
We have that $4\cdot \Phi_5(x)$ is pretty close to the square of $2x^2+x+2$, and indeed:

$$ 4 \Phi_5(x) = (2x^2+x+2)^2 - 5x^2 \tag{1}$$ as well as: $$ \Phi_5(x) = (x^2+3x+1)^2 - 5x(x+1)^2 \tag{2} $$ so if $x=5^{2k+1}$, $\Phi_5(x)$ is the difference of two large squares: $$\begin{eqnarray*} \Phi_5(5^{2k+1}) &=& \left(5^{4k+2}+3\cdot 5^{2k+1}+1\right)^2 - \left(5^{3k+2}+5^{k+1}\right)^2\\&=&\left(5^{4k+2}+5^{3k+2}+3\cdot 5^{2k+1}+5^{k+1}+1\right)\cdot\left(5^{4k+2}-5^{3k+2}+3\cdot 5^{2k+1}-5^{k+1}+1\right) \end{eqnarray*}$$ and $\Phi_5(5^{2k+1})$ cannot be a prime number. See Aurifeuillean factorization.


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.