## On Polynomials dividing Exponentials

EDIT: it turns out that no answer to this is known, as the authors of the book it is in have now confirmed they do not know how to do it. Will Jagy.

ORIGINAL: I have been wondering if there exist some general techniques to attack problems in which a polynomial divides and exponential equation. The motivation of this question came when trying to solve the following problem:

Find all positive integers "$m$ such that $m^2-1$ divides $3^m+5^m$

I haven't been able to come with a proof, and I am really considering the possibility that it cannot be solved using "elementary" methods.

I would really aprecciate some references (if there are any) to the general question as well as the solution to this very particular case.

-
Some general comments are to look at prime factorizations and the totient theorem, but I can't guarantee that that'll be enough in this case. – Qiaochu Yuan Feb 25 2010 at 1:32
If you found this problem in some standard puzzle source (e.g. an old olympiad or putnam problem) then there will be an elementary solution. If you're just making up a random equation in number theory and trying to solve it, then it might be incredibly hard. Look at FLT for example. Or even the question "find all primes p such that p^2 divides 2^p-2": these are the Wieferich primes, and not much is known about them other than what has been gleaned from computer computations. So I'm not very motivated to think about the question until I hear the source, and the general case is clearly hard! – Kevin Buzzard Feb 25 2010 at 8:13
Gabriel tends to prefer problems that may require some results usually introduced in "non-elementary" classes (e.g. irreducibility of the cyclotomic polynomials) but which have elementary proofs. So I would hold out for an elementary solution if I were you, depending on your precise definition of elementary. – Qiaochu Yuan Feb 25 2010 at 19:37
This is problem 4.8 in "Problems from the book", right? :) – Gjergji Zaimi Feb 26 2010 at 0:28
My comment above ("if it's in an Olympiad-style book then there's an elementary solution") has turned out to be false! – Kevin Buzzard Jul 1 2010 at 21:15

The source of the question is "Problems from the Book" by Andreescu and Dospinescu. I finally emailed Andreescu yesterday asking what was going on. He apologised---he says there's a typo in the book. He says he doesn't know how to answer the question. So I think the question should currently be regarded as an open problem. I'll remark that I made a comment under the original question which as I write has 11 upvotes and now has a serious chance of being false ;-)

-

Ok so Gjergji deleted his answer because it was mistaken at a critical point, but I was lucky enough to see it, and using one of the ideas in the answer I think one can prove that $m$ is odd. This is hence not an answer, but perhaps it's helpful.

Here's the proof. Say $m$ is even and $m^2-1$ divides $3^m+5^m$. Because $m$ is even we know $m^2-1$ is 3 mod 4, so it has a prime divisor $p$ congruent to 3 mod 4. Note that $p$ can't be 3, because 3 can't divide $3^m+5^m$. So $p\geq7$, and hence $5/3=\alpha$ is a unit mod $p$, with the property that $\alpha^m=-1$ mod $p$. But this means that $-1$ is a square mod $p$, as $m$ is even, and this is a contradiction (this is standard: if $-1$ is a square mod $p$ then the units mod $p$ have elements of order 4, so $p=1$ mod 4 as the order of an element divides the order of the group of units mod $p$). Done.

One can push mod powers of two a bit more. One checks easily that if $m$ is odd then $3^m+5^m$ is 8 mod 16. This implies that $m^2-1$ is also 8 mod 16 (as $m$ is odd so $m^2-1$ is a multiple of 8 and it had better not be a multiple of 16). Hence $m$ is 3 or 5 mod 8.

Finally, $3^m+5^m$ is coprime to 3, so $m^2-1$ had better be too, and hence $m$ is a multiple of 3. We deduce that modulo 24 $m$ is either 3 or 21.

-
Thanks for your interest in the problem. In fact I have been able to prove what you have said (I think I should have showed my approach). Then I also noted that the maximum power of two that divides $3^m+5^m$ with $m$ odd is $3$ so looking $mod 16$ ($m^2-1$ can't be a multiple of $16$) we find that $m \equiv 3,5 \bmod{8}$ and using the legendre symbol plus the quadratic reciprocity law we find some condition that $m$ must fullfill $mod 15$ – Daniel Kohen Feb 25 2010 at 20:41
Heh, I just edited my comments when I realised independently that I could do the same thing :-) – Kevin Buzzard Feb 25 2010 at 20:43
Mod 5 the condition is simply that $m$ isn't $+1$ or $-1$ mod 5, right? Or do you have something better? – Kevin Buzzard Feb 25 2010 at 20:43
For example if $m=8k+3$ and $m=5b$ then $m=120a+75$ $m^2-1=8(60a+37)(30a+19)$ Since $3^m \equiv -5^m \bmod{60a+37}$ $-15 \equiv x^2 \bmod{60a+37}$ Using Jacobi Symbol and the quadratic reciprocity law we find that: $\left({\frac{{-15}}{{60r+37}}}\right)= \left({\frac{{-1}}{{60a+37}}}\right) \left({\frac{{60a+37}}{{3}}}\right) \left({\frac{{60a+37}}{{5}}}\right)=(1)(1)(-1)=-1$ which contradicts the fact that $-15$ is a quadratic resiude. The same analysis might be used to discard some other combinations, though I'm not sure if it really helps a lot – Daniel Kohen Feb 25 2010 at 22:19
Stupid question Daniel: in your above argument how did you get from 3^m=-5^m mod 60a+37 to the fact that -15 was a square mod 60a+37? – Kevin Buzzard Feb 26 2010 at 7:38

I'm going to put these as a part answer and delete my earlier comments, I'm not sure people click on the "show 5 more comments," it took me weeks to notice that option, plus adding many comments did seem to slow the Latex font resolution. First, Kevin's initial argument showing that $m$ must be odd is readily reworded to show that $3^m + 5^m \neq 0 \pmod p$ for primes $p \equiv 7, 11, 43, 59 \pmod {60},$ as then $15, (5/3), (3/5)$ are all quadratic residues $\pmod p$ but $-1$ is not, so we simply never get $(5/3)^m \equiv -1 \pmod p$ for these primes.

Now adding in the fact that you have proved $m$ really must be odd in a genuine solution, we find that
$3^m + 5^m \neq 0 \pmod p$ for primes $p \equiv 13, 29, 37, 41 \pmod {60},$ as then $15, (5/3), (3/5)$ are all quadratic nonresidues $\pmod p$ but $-1$ is a residue, so with $m$ odd we never get $(5/3)^m \equiv -1 \pmod p$ for these primes either.

Put these together with everything else, we get $m \equiv 3,5 \pmod 8,$ then $m-1$ and $m+1$ cannot be divisible by 3 or 5 or by any prime $p$ with Legendre symbol $( -15 | p) = -1.$

In a similar spirit to Gjergji Zaimi, corollary to these observations got me as far as showing that $m \equiv 3, 93 \pmod {120},$ not quite optimal here.

It is also true that $m-1$ and $m+1$ cannot be divisible by 17 or 353 even though $-15$ is a quadratic residue here, these being primes $p \equiv 1 \pmod 4$ with the property that the smallest $m$ solving $(5/3)^m \equiv -1 \pmod p$ happens to be even, hence all possible such $m$ by a standard argument emphasizing the property of minimality. One has $p=17, \; m=2$ and $p=353, \; m=4$ and allowing larger $m$ we have $p=17, \; m \equiv 2 \pmod 4$ and $p=353, \; m \equiv 4 \pmod 8.$

Well, the strategy, a little less foolish than it seemed for a while, is to show that both $m-1$ and $m+1$ fail to be divisible by any odd primes in a genuine solution to the original problem, hence both are powers of 2, hence by inequalities $m=3.$ That is the hope anyway. The smallest uncertain prime is 19.

-

From the book sold here: http://awesomemath.org/xyz-press/ This is problem 8 on page 90, in Chapter 4 which is called "Primes and Squares." I bought the book, for quite a sum I might add. As Kevin found out, the authors do not know how to solve the problem!

Here is a cleaner version of the only stuff Kevin and I had so far that went anywhere.

First, if $m$ is even write $u = 3^{m/2}$ and $v = 5^{m/2},$ so that $$3^m + 5^m = u^2 + v^2.$$ Now $m^2 \equiv 0 \pmod 4$ and $m^2 - 1 \equiv 3 \pmod 4.$ Therefore there is some prime $q \equiv 3 \pmod 4$ such that $q | m^2 -1.$ This a contradiction, because $q | u^2 + v^2$ implies $q | u$ and $q | v$ but $\gcd(u,v)=1.$

As $m$ is now odd, $3^m + 5^m \equiv 3 + 5 \equiv 11 + 13 \equiv 8 \pmod {16}.$ So $m^2 - 1 \neq 0 \pmod {16}$ and $m \neq \pm 1 \pmod 8,$ therefore $m \equiv \pm 3 \pmod 8.$

As $3^m + 5^m \neq 0 \pmod {3,5}$ we know $m^2 - 1$ is not divisible by 3 or 5. With odd $m,$ write $m = 2 j + 1$ and then $$3^m + 5^m = 3 X^2 + 5 Y^2$$ with $X = 3^j$ and $Y = 5^j.$ As $\gcd(X,Y)=1$ and $3 x^2 + 5 y^2$ is a (primitive) binary quadratic form of discriminant $-60,$ it follows that $3 X^2 + 5 Y^2$ is not divisible by any prime $q$ with Jacobi symbol $$(-60 | q) = -1.$$ Note that, as $15 \equiv 3 \pmod 4,$ for primes $p \geq 7$ we have $$(-60 | p) = (-15 | p) = ( p | 15) .$$ Thus $m^2 - 1$ is not divisible by 3 or 5 or any prime $q$ with $( q | 15) = -1.$

As the restriction on prime factors applies to both $m-1$ and $m+1$ this is enough to show that possible $m > 3$ are quite rare. Both numbers are primitively represented by $r^2 + r s + 4 s^2$ or $2 r^2 + r s + 2 s^2.$

So $m$ itself is divisible by 3. Consider the odd number $w = (m^2 - 1)/8.$ If $m$ were also divisible by 5, we would have $$w \equiv \frac{-1}{8} \equiv 13 \pmod {15}.$$ So then we would have $( w | 15) = -1$ which would mean the existence of some prime $q$ with $q | w$ and $(q | 15) = -1.$ But then we would have $q | m^2 - 1$ which is prohibited. So $m \equiv 0 \pmod 3$ and $m \equiv \pm 3 \pmod 5.$

-

The only m I've found that works up to 10,000 is 3, but I can't prove that it's the only one.
While I don't know how solve it directly, the exponential equation can be transformed into: $5^m + 3^m = 5^m\left(1+m!\sum _{k=0}^m \frac{(-2)^k}{k!(m-k)!5^k}\right)$, so you're looking for integer results to $\frac{5^m}{m^2-1}+m\frac{(m-2)!}{m+1}\left(\sum _{k=0}^m \frac{(-2)^k5^m}{k!(m-k)!5^k}\right)$.
The general form of the first equation here is: $a^m + b^m = a^m\left(1+m!\sum _{k=0}^m \frac{(b-a)^k}{k!(m-k)!a^k}\right)$, assuming ab (if a = b, then the numerator for k = 0, the numerator of the sum would be 00 which should turn into 1). I would think that this might be a bit easier to solve, but I can't be sure.

Hope this helps!
-Gabriel Benamy

-