Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Does the equation $x^m-1=y^n+y^{n-1}+...+1$ have only finitely many solutions $(x,y,m,n)$ where $x,y$ are prime powers with $y>2$ and $m,n$ are integers with $m,n>1$?

This question arose in the study a group theory problem, where I'm examining a "natural" subgroup $G$ of $S_d$ where $d:=x^m-1$. I can show that $G$ is primitive and contains a $d$-cycle, so if $d$ is composite then known results imply that $G$ must be either $S_d$ or $A_d$ or a group between $\text{PGL}_{n+1}(y)$ and its automorphism group, for some $(n,y)$ satisfying the above equation. I'm hoping to show that the last case almost never happens. The best I can do so far is the simple observation that if $m=2$ then the set of prime $x$'s for which the equation has a solution is a density-zero subset of the primes. But I'm hoping that a much stronger result is possible.

share|improve this question
    
The wording is a little unclear as to whether $m, n$ are fixed or whether you want "finitely many" to apply to tuples $(x, y, m, n)$. If they're fixed, then finiteness follows for all but finitely many pairs $(m, n)$ by Faltings' theorem, although this is a sledgehammer. –  Qiaochu Yuan Nov 4 '13 at 22:39
1  
This looks close enough to Catalan's conjecture that you might check out Ribenboim's book. He has a lot of ancillary material; you might find something useful there. –  The Masked Avenger Nov 4 '13 at 23:06
4  
I suspect this is quite hard (though, as my daughter is quick to point out, I'm frequently mistaken). The arguments that get you off the ground for Catalan are very sensitive and, for instance, don't get you anywhere for the equation $x^n-y^m=2$. The beast you're after is, in the case $n=2$, essentially the Ramanujan-Nagell equation (where the assumption that $x$ is prime does, admittedly, simplify things). –  Mike Bennett Nov 5 '13 at 4:52
1  
As another comparison, if you just replace your left-hand-side $x^m-1$ by $x^m$, you would have the Nagell-Ljunggren equation (which also shows up in group theory). This equation is, on the surface, a little easier to attack than the one you are considering, but is still unsolved even in the sense that it is unknown whether the number of solutions (in four variables) is finite. –  Mike Bennett Nov 5 '13 at 21:27
1  
If you want $y$ to be an odd prime power, then, assuming $x=4$, you have that $n$ is even and so we can apply Runge's method (assuming you can prove the necessary irreducibility, which I think is OK). One gets a bound like $2^m \ll 12^n$ or something similar, which bounds $y$, unless I've messed up. –  Mike Bennett Nov 6 '13 at 2:00

2 Answers 2

up vote 1 down vote accepted

Mike Bennett's comments gives good reason to suspect that my original question is beyond what can be proved with existing techniques. Here I record one thing that can be proved (again thanks to Mike's comment), namely that there are no solutions with $x=4$. That is: the equation $4^m-1=y^n+y^{n-1}+...+1$ has no solutions $(y,m,n)$ in which $y$ is a prime power with $y>2$ and $m,n$ are integers with $m,n>1$.

Suppose that $(y,m,n)$ is a solution. First note that $y$ is odd and $n$ is even. For, if $y$ were even then we would contradict uniqueness of base-$2$ expansion by writing the number $4^m-1$ in two different ways as the sum of distinct powers of $2$, namely as both $2^{2m-1}+2^{2m-2}+...+1$ and $y^n+y^{n-1}+...+1$. Hence $y$ is odd, so the mod $2$ reduction of the equation $4^m-1=y^n+y^{n-1}+...+1$ implies that $n$ is even.

Next show that the polynomial $X^2-1-(Y^n+Y^{n-1}+...+1)$ is irreducible in $\mathbf{Q}[X,Y]$. If it were reducible then it must factor as $(X-f(Y))\cdot(X+f(Y))$ for some polynomial $f(Y)$, so that $f(Y)^2=1+(Y^n+Y^{n-1}+...+1)$ is a square in $\mathbf{Q}[Y]$. Rewrite this as $1+(Y^{n+1}-1)/(Y-1)$, or equivalently $(Y^{n+1}+Y-2)/(Y-1)$. Then $f(Y)$ divides both $Y^{n+1}+Y-2$ and its derivative $(n+1)Y^n+1$, so $f(Y)$ also divides $(n+1)\cdot(Y^{n+1}+Y-2) - Y\cdot((n+1)Y^n+1)=nY-2(n+1)$, whence $\deg(f)=1$ so $n=2\deg(f)=2$. But $Y^2+Y+2$ is not a square in $\mathbf{Q}[Y]$, contradiction.

Now we can apply Theorem 4.1(ii) of the paper "Estimates for the solutions of certain Diophantine equations by Runge's method" by A.Sankaranarayan and N.Saradha (Int.J.Number Theory 4 (2008), 475-493). According to this result (which uses the condition that $n$ is even), if $u,v$ are integers such that $u^2-1=v^n+v^{n-1}+...+1$, then $|u|\le 2^{3n+4}$.  But we know that $(u,v)=(2^m,y)$ is a solution, so $2^m\le 2^{3n+4}$.  On the other hand we have $y^n<4^m$, so that $y^n<4^{3n+4}$ and thus $y<4^{3+(4/n)}$.  I checked via computer that there are no solutions with $n<44$. So assume $n\ge 44$, which implies that $y<73$.

Since $4^m=(y^n+y^{n-1}+...+y)+2$, we have $4^m\equiv 2\pmod{y}$, so the order of $2$ in $(\mathbf{Z}/y\mathbf{Z})^*$ is odd. Since $y<73$, it follows that $y\in\{7,23,31,47,49,71\}$. Each of these values $y$ satisfies either $y\equiv -1\pmod{4}$ or $y\equiv -1\pmod{5}$. If $y\equiv -1\pmod{4}$ then, since $n$ is even, we obtain the contradiction $4^m=(y^n+y^{n-1}+...+y)+2\equiv 2\pmod{4}$. Likewise, if $y\equiv -1\pmod{5}$ then $(y^n+y^{n-1}+...+y)+2\equiv 2\pmod{5}$, so that $4^m\equiv 2\pmod{5}$, which is impossible.

(Note: the Sankaranarayan-Saradha result is a refinement of an earlier result by P.G.Walsh; if one uses Walsh's result, then the same proof works except that one must rule out $y=73$ by a different method. One way to do this is to note that the equation $4^m-1\equiv 73^n+73^{n-1}+...+1\pmod{91}$ has no solutions in which $n$ is even.)

share|improve this answer

This is too long for a comment so I will post it as an answer. More precisely, consider the equation $$x^n-1=\frac{y^q-1}{y-1},$$ In what follows, I will assume that $q$ is prime but this condition can be weakened. Note, if a prime $r|\frac{y^q-1}{y-1}$ then by Fermat Little Theorem we have that either $r|q$ or $q|r-1$ and thus $r=qk+1.$

Suppose $y\ne 1(\mod q),$ then $\frac{y^q-1}{y-1}=\frac{y-1}{y-1}=1 (\mod q)$ and we must have $x^n-1=1(\mod q)$ or $x^n=2(\mod q).$ But $x-1|\frac{y^q-1}{y-1}$ and so all prime divisors of $x-1$ are congruent to $1(\mod q).$ Thus, $x-1=1(\mod q)$ which implies that $2^n=2(\mod q).$ So if $2^n\ne 2(\mod q)$ our equation has no solutions.

Now, if $y=1 (\mod q),$ we have $\frac{y^q-1}{y-1}=0(\mod q)$ and we must have $x^n=1(\mod q).$ Moreover, $x^n-1=(x-1)(x^{n-1}+....+1)$ and since all prime divisors of both $x-1$ and $x^{n-1}+x^{n-2}+...+1$ are either $q$ or $r=1(\mod q),$ we must have $x-1=0,1(\mod q)$ and $x^{n-1}+....+1=0,1(\mod q).$

If $x=1(\mod q),$ we must have $n=1,0(\mod q).$ If $x=2(\mod q),$ we must have $2^n=1(\mod q.)$ Otherwise, there are no solutions.

For the general, if $q$ is not prime, we get that prime divisors of the right had sides come from divisors of $q$ or different arithmetic progressions with differences dividing $n.$ One may perform similar analysis in some particular cases.

share|improve this answer
    
Thanks, all of that makes sense. –  Michael Zieve Nov 7 '13 at 5:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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