# May $p^3$ divide $(a+b)^p-a^p-b^p$?

Do there exist positive integers $a,b$ and a prime $p>\max(a,b)$ such that $p^3$ divides $(a+b)^p-a^p-b^p$?

The reader of Kvant magazine A. T. Kurgansky asked to prove that such $a,b,p$ do not exist, see here. But discussion here

On the exact reference of a cute Diophantine problem

suggests that it should be very hard to prove. Maybe, a counterexample may be bound? Roughly speaking, a probability of this event is about $1/p^2$, for each $p$ we have about $p$ events (even for $b=1$, I was previously wrong that it may be supposed without loss of generality, thanks for Noam Elkies for noting this) and so as $\sum 1/p=\infty$, we may expect them (and even infinitely many!) But this series converges very slowly, so the minimal example may be large.

• How far has it been checked numerically? Computing power is much more plentiful now than it was in 1984. – Noam D. Elkies Nov 29 '16 at 14:54
• That does not preserve congruences mod $p^3$. – Noam D. Elkies Nov 29 '16 at 14:57
• "We may suppose that $b=1$" -- I don't see it: replacing $(a,b)$ by $(a/b,1) \bmod p^2$ won't usually preserve the region $a,b \leq p$. – Noam D. Elkies Nov 29 '16 at 15:00
• @NoamD.Elkies you are correct: of course, we can not assume this. Moreover, finding a root $x$ of $((x+1)^p-x^p-1)/p$ modulo $p^2$, if it exists, we may choose a pair $(a,b)=(a\mod p^2,ax \mod p^2)$ for appropriate $a$, and something like that works or almost works by Thue's lemma. – Fedor Petrov Nov 29 '16 at 15:09
• @AlexeyUstinov what exactly is the question? Of course we may always add $p^3$ to $a,b$. – Fedor Petrov Nov 30 '16 at 15:01

There are apparently lots of examples. The smallest is $a=1$, $b=2$, and $p=7$.

• The cutest small example was $a=5$, $b=6$, and $p=7$. – Pace Nielsen Nov 29 '16 at 14:58
• Great. I did not expect that they missed such a small example. – Fedor Petrov Nov 29 '16 at 15:02
• Pace Pace Nielsen, arguably $(a,b,p) = (3,5,7)$ is even cuter, besides being the first example where $(a+b)^p - a^p - b^p$ is divisible not just by $p^3$ but even by $p^5$. – Noam D. Elkies Nov 29 '16 at 22:23
• Wow -- computers must have been pretty rubbish in 1984... – wrigley Nov 30 '16 at 9:26

We explain the pattern observed by Joe Silverman, deducing the existence of infinitely many solutions, some of which even have $p^5 | (a+b)^p - a^p - b^p$.

Lemma. If $n \equiv 1 \bmod 3$ then the homogeneous polynomial $P_n(a,b) := (a+b)^n - a^n - b^n \in {\bf Z}[a,b]$ has a factor $(a^2+ab+b^2)^2$.

Proof : Either
i) evaluate $P_n(x,1)$ and its derivative at a cube root of unity $\rho$, or
ii) use the $S_3$ symmetry of $-P_n(a,b) = a^n + b^n + c^n$ where $a+b+c=0$: double roots at $(a:b:c) = (1:\rho:\rho^2)$ and $(1:\rho^2:\rho)$ are the only ways to get the total number of roots to be $1 \bmod 3$. $\Box$

[These ${\bf Q}(\rho)$-rational points on the $n$-th Fermat curve are well known.]

Corollary. If $p$ is a prime congruent to $1 \bmod 3$, and $a,b$ are integers such that $p^k | a^2+ab+b^2$, then $p^{2k+1} | P_n(a,b)$.

Proof : Observe that $P_p \in p {\bf Z}[a,b]$ and use the Lemma.

Now $k=1$, and thus $2k+1=3$, is easy to obtain: choose $a$ arbitrarily, and let $b\equiv ra \bmod p$ where $r$ is a cube root of unity mod $p$. We can even get a factor of $p^5$ by choosing $a,b$ such that $a^2 + ab + b^2 = p^2$ (that is, so that $a,b,p$ are sides of a triangle with a $120^\circ$ angle); for example, $$(3+5)^7 - 3^7 - 5^7 = 120 \cdot 7^5.$$

• Yes of course (or as we'd do it nowadays, by applying Hensel's Lemma), but once $k>2$ we can no longer find positive solutions with $a,b < p$ as the Kvant problem asked. – Noam D. Elkies Nov 29 '16 at 18:30
• For the first 200 primes I find by exhaustive search that there is no solution mod $p^6$ with $0<a,b<p$. – Neil Strickland Nov 29 '16 at 18:53
• Motivated by Neil's computation, I've now checked all primes up to $8803$, and there are still no solutions modulo $p^6$. – Pace Nielsen Dec 2 '16 at 14:50

For what it's worth, consider $b=p-1$. It seems (experimentally at least, I haven't tried to prove it) that for every $p\equiv1\pmod6$ there exists an $a$ in the range $2\le a\le \frac{1}{2}p$ such that $$(a+p-1)^p-a^p-(p-1)^p\equiv0\pmod{p^3}.\qquad (*)$$ I checked for $p<500$, and in this range, for each $p$ there is a unique such $a$. Further, again just for $p<500$, if $p\not\equiv1\pmod6$, then there are no solutions to $(*)$.

• The unique solution is always a cube root of unity mod $p$ (verified up to $1000$ now); presumably it's easy to prove in general that this works, and intractable to show that there are no other solutions. – Noam D. Elkies Nov 29 '16 at 15:59
• (Actually that was for $b=1$. For $b=p-1$ it's a sixth root of unity.) – Noam D. Elkies Nov 29 '16 at 16:02
• Interesting. This congruence is equivalent to $(a-1)^p-a^p+1\equiv 0\pmod p^3$, or $a+a^2/2+\dots+a^{p-1}/(p-1)\equiv 0 \pmod p^2$. But I do not see why it has roots modulo $p^2$ so often and why $p$ modulo 3 matters. – Fedor Petrov Nov 29 '16 at 16:05
• Well, why the cubic root of unity works is seen from this formula. – Fedor Petrov Nov 29 '16 at 16:07
• @NoamD.Elkies Thanks. I was going to try to figure out what the $a$ was when I got a chance. I'm not actually convinced of the uniqueness. – Joe Silverman Nov 29 '16 at 16:07