# On Polynomials dividing Exponentials

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.

-
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 '10 at 8:13
There used to be an answer by me, where I kept making erroneous claims.. – Gjergji Zaimi Feb 25 '10 at 12:57
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 '10 at 19:37
This is problem 4.8 in "Problems from the book", right? :) – Gjergji Zaimi Feb 26 '10 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 '10 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 ;-)

-
What is exactly this typo? I wonder how the problem is formulated if the typo is fixed. – Max Alekseyev May 20 '15 at 2:48
@MaxAlekseyev, see one of my answers, I pasted in the page with the actual problem. I also put a link to the current (second) edition of the book, which I do not plan to purchase. Since the problem did not work out, they may simply have deleted it for the second edition without comment. For more information, it would be necessary to contact Andreescu or Dospinescu. – Will Jagy May 20 '15 at 19:12
@WillJagy: Thanks for the exact pointer. I happen to have the second edition and the problem 5 (ex-8) there is formulated as $m^2-1\mid 3^m + (n!-2)^m$. – Max Alekseyev May 20 '15 at 20:10
@MaxAlekseyev, aha! So it may really have been a typo in the first edition, just a single number different. That makes me feel a bit better about the authors; in 2010 I was less than charitable (then deleted some stuff here). – Will Jagy May 20 '15 at 20:15

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 '10 at 20:41
Heh, I just edited my comments when I realised independently that I could do the same thing :-) – Kevin Buzzard Feb 25 '10 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 '10 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 '10 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 '10 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 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.$

-
The link doesn't seem to go anywhere any more. – Gerry Myerson May 20 '15 at 13:11
@GerryMyerson, I fixed the link, however it points to a second edition of the book, which probably lacks this problem. I have a scanner, I imagine the thing to do is scan in the page from the first edition with this exact problem. – Will Jagy May 20 '15 at 18:32
@GerryMyerson, Max Alekseyev has the second edition of the book, and says the corrected question reads $$m^2 - 1 \; | \; 3^m + \left( n! - 2 \right)^m,$$ so it really is off by just a single number and was a typo in the first edition. Good to know. – Will Jagy May 20 '15 at 20:20

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

-

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$.

-