On Polynomials dividing Exponentials

Question

EDIT, May 2015: in the second edition of the relevant book, the question was corrected, a single number had been mis-typed. The corrected question (thanks to Max) is to find all positive integer pairs such that $$ m^2 - 1 \; | \; 3^m + \left( n! - 2 \right)^m. $$ $$ $$ The version that caused me all that misery was $ m^2 - 1 \; | \; 3^m + \left( n! - 1 \right)^m. $

EDIT, 2010: 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.

Answer 1

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 ;-)

Answer 2

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.

Answer 3

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.

Answer 4

From the first edition of the book sold here, which is now the second edition: 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.$

May 2015: here is the page from the first edition of the relevant book. The OP said that he first saw the problem elsewhere, which is quite possible. In problem 11, $P_3$ is the set of primes $q \equiv 3 \pmod 4.$

Answer 5

Just an extended comment:

Since $m$ is odd, we have $(3^m+5^m)\mid (3^{m^2}+5^{m^2})$ and thus $(m^2-1)\mid (3^{m^2}+5^{m^2})$. In other words, both $m$ and $m^2$ must belong to the set $$S=\{ n\in\mathbb{N} : (n-1)\mid (3^n+5^n)\},$$ which is represented by the sequence http://oeis.org/A234535 in the OEIS.

It is therefore interesting to consider a (possibly simpler) question of finding all squares in $S$.

Answer 6

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 a ≠ b (if a = b, then the numerator for k = 0, the numerator of the sum would be 0⁰ 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