8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How far has it been checked numerically? Computing power is much more plentiful now than it was in 1984. $\endgroup$ – Noam D. Elkies Nov 29 '16 at 14:54
  • 1
    $\begingroup$ That does not preserve congruences mod $p^3$. $\endgroup$ – Noam D. Elkies Nov 29 '16 at 14:57
  • 1
    $\begingroup$ "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$. $\endgroup$ – Noam D. Elkies Nov 29 '16 at 15:00
  • $\begingroup$ @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. $\endgroup$ – Fedor Petrov Nov 29 '16 at 15:09
  • $\begingroup$ @AlexeyUstinov what exactly is the question? Of course we may always add $p^3$ to $a,b$. $\endgroup$ – Fedor Petrov Nov 30 '16 at 15:01
13
$\begingroup$

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

$\endgroup$
  • 5
    $\begingroup$ The cutest small example was $a=5$, $b=6$, and $p=7$. $\endgroup$ – Pace Nielsen Nov 29 '16 at 14:58
  • 1
    $\begingroup$ Great. I did not expect that they missed such a small example. $\endgroup$ – Fedor Petrov Nov 29 '16 at 15:02
  • 3
    $\begingroup$ 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$. $\endgroup$ – Noam D. Elkies Nov 29 '16 at 22:23
  • $\begingroup$ Wow -- computers must have been pretty rubbish in 1984... $\endgroup$ – wrigley Nov 30 '16 at 9:26
20
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Noam D. Elkies Nov 29 '16 at 18:30
  • $\begingroup$ For the first 200 primes I find by exhaustive search that there is no solution mod $p^6$ with $0<a,b<p$. $\endgroup$ – Neil Strickland Nov 29 '16 at 18:53
  • $\begingroup$ Motivated by Neil's computation, I've now checked all primes up to $8803$, and there are still no solutions modulo $p^6$. $\endgroup$ – Pace Nielsen Dec 2 '16 at 14:50
10
$\begingroup$

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 $(*)$.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Noam D. Elkies Nov 29 '16 at 15:59
  • $\begingroup$ (Actually that was for $b=1$. For $b=p-1$ it's a sixth root of unity.) $\endgroup$ – Noam D. Elkies Nov 29 '16 at 16:02
  • $\begingroup$ 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. $\endgroup$ – Fedor Petrov Nov 29 '16 at 16:05
  • $\begingroup$ Well, why the cubic root of unity works is seen from this formula. $\endgroup$ – Fedor Petrov Nov 29 '16 at 16:07
  • $\begingroup$ @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. $\endgroup$ – Joe Silverman Nov 29 '16 at 16:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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