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.

Improve this question
$\endgroup$
6
  • $\begingroup$ How far has it been checked numerically? Computing power is much more plentiful now than it was in 1984. $\endgroup$
    – Noam D. Elkies
    Commented Nov 29, 2016 at 14:54
  • 1
    $\begingroup$ That does not preserve congruences mod $p^3$. $\endgroup$
    – Noam D. Elkies
    Commented 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$
    – Noam D. Elkies
    Commented 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$
    – Fedor Petrov
    Commented 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$
    – Fedor Petrov
    Commented Nov 30, 2016 at 15:01

3 Answers 3

Reset to default
13
$\begingroup$

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

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

Improve this answer
$\endgroup$
4
  • 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
    Commented 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$
    – Neil Strickland
    Commented 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$
    – Pace Nielsen
    Commented Dec 2, 2016 at 14:50
  • $\begingroup$ I have checked all primes up to a million and found no solutions for $p^6 \mid a^2 + ab + b^2$ with $a, b$ integers such that $0 < a, b < p$. The code can be found here: github.com/TiagoCavalcante/freshmans_nightmare A better machine could test for many more primes, and the code can also be converted to run on the GPU. TL;DR This conjecture is probably true and can be verified for something around the primes smaller than a billion if there is any interest. $\endgroup$
    – Tiago Cavalcante
    Commented Apr 12 at 1:57
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 $(*)$.

Improve this answer
$\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$
    – Noam D. Elkies
    Commented 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$
    – Noam D. Elkies
    Commented 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$
    – Fedor Petrov
    Commented Nov 29, 2016 at 16:05
  • $\begingroup$ Well, why the cubic root of unity works is seen from this formula. $\endgroup$
    – Fedor Petrov
    Commented 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$
    – Joe Silverman
    Commented Nov 29, 2016 at 16:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .