Prove that $\dfrac {\left( 5^{125}-1\right)}{\left( 5^{25}-1\right)}$ is composite number using number theory. Do not use calculator or Wolfram alpha or anything like that.
$\begingroup$
$\endgroup$
5
-
1$\begingroup$ What is composite number? $\endgroup$– amir bahadoryCommented Jul 1, 2015 at 11:00
-
$\begingroup$ A composite number is an integer which is NOT a prime number. $\endgroup$– Akshay HegdeCommented Jul 1, 2015 at 11:02
-
1$\begingroup$ if $x=5^{25}$ then your formula gives $\frac{x^5-1}{x-1}$ right? $\endgroup$– Clément GuérinCommented Jul 1, 2015 at 11:04
-
$\begingroup$ Yes! correct. Go ahead. $\endgroup$– Akshay HegdeCommented Jul 1, 2015 at 11:05
-
$\begingroup$ @AkshayHegde use that fact with this answer here $\endgroup$– Chinny84Commented Jul 1, 2015 at 11:07
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
0
Hint $\ $ The factorization arises by applying a variation of cyclotomic factorization known as Aurifeuillian factorization (aka Aurifeuillean). For the OP we can employ the following one
$$\begin{align}\frac{(5x^2)^5-1}{5x^2-1} =\, (25x^4\!+15x^2+1)^2 - (5x(5x^2\!+1))^2\\[4pt] \overset{\large x\, =\, 5^{\large 12}}\Longrightarrow\ \ \frac{5^{125}-1}{5^{25}-1}\, =\, (5^{50}+3\cdot 5^{25}+1)^2 - (5^{13}(5^{25}+1))^2\end{align}$$
Remark $\ $ There are many known Aurifeuillian factorizations (e.g. see below for a few more). For more see this answer and see Aurifeuillian Factorization by A. Granville and P. Pleasants.
$$\begin{align} \frac{(3x^2)^3+1}{3x^2+1} &=\, (3x^2\!+1)^2-(3x)^2\\[4pt] \frac{(5x^2)^5-1}{5x^2-1} &=\, (25x^4\!+15x^2+1)^2 - (5x)^2(5x^2\!+1)^2\\[4pt] \frac{(7x^2)^7+1}{7x^2+1} &=\, (7x^2\!+1)^6-(7x)^2(49 x^4\!+7x^2+1)^2 \end{align}$$
answered Jul 1, 2015 at 15:41
$\begingroup$
$\endgroup$
7
This is problem $87$ of Putnam and Beyond. Here is the solution:
$\dfrac{5^{125}-1}{5^{25}-1}=1+a+a^2+a^3+a^4$ where $a=5^{25}$.
We have $1+a+a^2+a^3+a^4+a^5=(a^2+3a+1)^2-(5^{13}(a+1))^2=(a^2+3a+1+5^{13}(a+1))(a^2+3a+1-5^{13}(a+1))$
The reason the second factor is larger than $1$ is $a^2=5^{50}>5^{39}>5^{13}(a+1)$
This problem was also part of the 1992 imo shortlist and was proposed by Korea, here is a link with the same solution but shorter: https://mks.mff.cuni.cz/kalva/short/soln/sh9216.html
-
3$\begingroup$ Wow, now how were you expected to realize that as a difference of squares in the first place? Is it just a puzzle-math mantra that that's one of the first things you try on such a problem? $\endgroup$ Commented Jul 1, 2015 at 11:17
-
1$\begingroup$ @gamamal Thanks a lot for the solution and citing the source. I came across it in a local math competition. $\endgroup$ Commented Jul 1, 2015 at 11:28
-
2$\begingroup$ No problem, happy to help. Wow, those are some hardcore local competitions ! $\endgroup$– AsinomásCommented Jul 1, 2015 at 11:29
-
1$\begingroup$ (+1) @Gamamal, the trick was to show that $1 + a + a^2 + a^3 + a^4 = xy$ as in can be written as a product of two other numbers? Which would show it isnt prime? Another Question - Can proof by contradiction be used in such cases? $\endgroup$– Amad27Commented Jul 1, 2015 at 11:32
-
4$\begingroup$ This is a special case of a general class of factorizations - see my answer. $\endgroup$ Commented Jul 1, 2015 at 15:41
$\begingroup$
$\endgroup$
1
HINT:
$x^5-1=(x-1)(x^4+x^3+x^2+x+1)$
and $5^{25}=(5^5)^5$, whilst $5^{125}=((5^5)^5)^5$
Does this get you anywhere?
-
2$\begingroup$ $x^4+x^3+x^2+x+1$ can be prime, for example when x = 7. So now you figure out why x = $5^{25}$ is special. $\endgroup$ Commented Jul 1, 2015 at 16:00
$\begingroup$
$\endgroup$
Put $x = 525$. Then $\frac{5^{125}-1}{5^{25}-1} = x^4+x^3+x^2+x+1 = (x^2+3^x+1)^2 - 5x(x+1)^2$ which has factor $(x^2+3x+1-513x-513)$ which is obviously $> 1$ and $< x^4+x^3+x^2+x+1$.
