Prove that the equation \[ x^n + 1 = y^{n+1}, \] where $n$ is a positive integer not smaller then 2, has no positive integer solutions in $x$ and $y$ for which $x$ and $n+1$ are relatively prime.
Problem
Source: IMO 1980 Finland, problem 3
Tags: number theory, equation, algebra, Diophantine equation, IMO Shortlist
06.05.2004 19:27
(y-1)(y^n+...+y+1)=x^n (1) gcd(y-1,y^n+...+y+1)=1 proof: assume that gcd(y-1,y^n+...+y+1)>1, let p be a common prime divisor on one hand y==1(mod p) ==> y^n+...+y+1==n+1==0(mod p) on the other hand p|x contradiction because gcd(x,n+1)=1 (2) from (1) it follows that y^n+...+y+1=z^n for some positive integer z, which is impossible because y^n < y^n+...+y+1 < (y+1)^n Therefore there are no positive integer solutions.
16.11.2005 21:28
See also here http://www.mathlinks.ro/Forum/viewtopic.php?t=45697
23.09.2017 21:54
It can be also solved by using Euler's totient theorem very easily. First assume x to be prime or prime to the power of something. Then applying inequality.
07.06.2018 06:19
Suppose $n=p-1$ for any odd prime $p$. Then we have, $$x^{p-1} \equiv 1 \pmod {p}\implies y^p-2 \equiv 0\pmod{p}$$Then we have, $$y \equiv 3 \pmod {p}$$If $p$ is odd we must have $x$ even implying $y$ even. Contradiction. If $p=2$, we have $n<2$. Contradiction. If $n=p$, for some odd integer $p$. $$x^{p}+1 \equiv y^{p+1} \pmod{p}$$We must have $x$ odd.Then, we see that $y$ is even. $$x^{\phi{p}} \equiv 1 \pmod{p}$$I can't see motivation to proceed. Can anyone help me?
17.03.2020 03:32
Note that this is equivalent to $x^n=y^{n+1}-1=(y-1)(y^n+y^{n-1}+...+y+1)$. Lemma: $\gcd{(y^n+y^{n-1}+...+y+1,y-1)}=\gcd{(y-1,n+1)}$. Proof of Lemma: Using Euclidian Algorithm, \begin{align*}\gcd{(y^n+y^{n-1}+...+y+1,y-1)}&=\gcd{((-y^n+y^{n-1})+y^n+y^{n-1}+...+y+1,y-1)}\\&=\gcd{(y^{n-1}+(y^{n-1}+...+y+1,y-1))}.\end{align*}It's easy to see that we can continuously replace $y^k$ with $y^{k-1}$ while keeping the $\gcd$, so we result with $n+1$ (as we started with $n+1$ terms. $\blacksquare$ From the Lemma and the problem condition that $\gcd{(x,n+1)}=1$, $\gcd{(y^n+y^{n-1}+...+y+1,y-1)}=1$. We see that $y-1\mid x^n$, so unless $y-1=1$ or $y^n+y^{n-1}+...+y+1=1$, the latter of which is absurd, there does not exist a solution. So we conclude that $y=2,$ if any solution exists. Now we wish to find solutions to $$x^n+1=2^{n+1}.$$It's obvious that $x$ must be odd for this to be true. But then note that $x\geq 3\implies x^n\geq 2^{n+1}$ for $n\geq 2$ and $x\geq 5\implies x^n\geq 2^{n+1}$ for $n\geq 1$, so if any solution exists then (by the problem condition for $n$) $n=2$ and $x=3$ or $x=1$, both of which clearly do not work, and we may conclude.
19.11.2024 21:19
By Mihaelescu, the only consecutive perfect powers are $8$ and $9$ which do not satisfy the conditions of the problem.