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

3 Answers 3

13
$\begingroup$

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

$\endgroup$
4
  • 6
    $\begingroup$ The cutest small example was $a=5$, $b=6$, and $p=7$. $\endgroup$ Nov 29, 2016 at 14:58
  • 1
    $\begingroup$ Great. I did not expect that they missed such a small example. $\endgroup$ Nov 29, 2016 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$ Nov 29, 2016 at 22:23
  • $\begingroup$ Wow -- computers must have been pretty rubbish in 1984... $\endgroup$
    – wrigley
    Nov 30, 2016 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$
3
  • 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$ Nov 29, 2016 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$ Nov 29, 2016 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$ Dec 2, 2016 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$
8
  • 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$ Nov 29, 2016 at 15:59
  • $\begingroup$ (Actually that was for $b=1$. For $b=p-1$ it's a sixth root of unity.) $\endgroup$ Nov 29, 2016 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$ Nov 29, 2016 at 16:05
  • $\begingroup$ Well, why the cubic root of unity works is seen from this formula. $\endgroup$ Nov 29, 2016 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$ Nov 29, 2016 at 16:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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