Some links with spoilers killing this problem: http://artofproblemsolving.com/community/c194913h1319556 (for people in WOOT) http://math.stackexchange.com/questions/1961526 (linked to in the WOOT post)

Darn, sorry about that

rafayaashary1 wrote: Wait, why can't we just choose $(a,b)=(p^3-1,1)$? Because $a<p$ and $b<p$

How was this on the TST? Isn't this super well known. The key lemma is essentially to try and factor out $(x^2+x+1)^2|((x+1)^p-x^p-1)$ and using derivatives this is obvious.

mssmath wrote: How was this on the TST? Isn't this super well known. The key lemma is essentially to try and factor out $(x^2+x+1)^2|((x+1)^p-x^p-1)$ and using derivatives this is obvious. Could you elaborate, please?

mssmath wrote: How was this on TST? Isn't this super well known. This problem was on TST because it was test-solved by (at least) nine different graders and instructors, including me. Less than half of them solved it, and in particular I spent five hours on the problem and was not able to find a solution. The problem was generally positively received and none of the graders reported having seen it before. As the student's scores on the problem were largely zero too (I do not have an exact count here), I think this is definitive proof that the problem is not "super well-known".

I guess this reminded he so much of the $7^{7^n}$ USAMO problem and the analogous factorization (The factorization in that problem and this are closely related.)

mssmath wrote: I guess this reminded he so much of the $7^{7^n}$ USAMO problem and the analogous factorization (The factorization in that problem and this are closely related.) Huh, I don't actually see the connection. Can you elaborate? For me, the trigger should have been the solution to ELMO 2009/6. The problem actually crossed my mind while I was test-solving, but I didn't make the connection. Granted, I had been working at a noisy conference, and maybe would have found it on a better day (or maybe I'm just deluding myself ).

artsolver wrote: mssmath wrote: How was this on the TST? Isn't this super well known. The key lemma is essentially to try and factor out $(x^2+x+1)^2|((x+1)^p-x^p-1)$ and using derivatives this is obvious. Could you elaborate, please? Here's a full solution. The key claim is that if $p \equiv 1 \pmod 3$, then \[ p(x^2+xy+y^2)^2 \text{ divides } (x+y)^p - x^p - y^p \]as polynomials in $x$ and $y$. Since it's known that one can select $a$ and $b$ such that $p^2 \mid a^2 + ab + b^2$, the conclusion follows. (The theory of quadratic forms tells us we can do it with $p^2 = a^2+ab+b^2$; Thue's lemma lets us do it by solving $x^2+x+1 \equiv 0 \pmod{p^2}$.) To prove this, it is the same to show that \[ (x^2+x+1)^2 \text{ divides } F(x) \overset{\text{def}}{=} (x+1)^p - x^p - 1. \]since the binomial coefficients $\binom pk$ are clearly divisible by $p$. Let $\zeta$ be a third root of unity. Then $F(\zeta) = (1+\zeta)^p - \zeta^p - 1 = -\zeta^2 - \zeta - 1 = 0$. Moreover, $F'(x) = p(x+1)^{p-1} - px^{p-1}$, so $F'(\zeta) = p - p = 0$. Hence $\zeta$ is a double root of $F$ as needed.

Oops I lied I misremembered where I saw this. http://www.cs.cornell.edu/~asdas/imo/imo/isoln/isoln842.html Old IMO's can apparently be useful.

Here's some motivation for v_Enhance's solution (since mine was pretty much the same): First we can WLOG $y=1$, as otherwise we can replace $(a,b)$ with $\left(\frac{a}{b}, 1\right)\pmod{p}$. Thus, we want a value of $X$ such that $p^3\mid (X+1)^p-X^p-1$. Let $f(X)=\frac{1}{p}[(X+1)^p-X^p-1]$. If we can find some polynomial $a(X)$ with $a(X)^2\mid f(X)$, then we are done. In other words, we want $f(X)$ and $f'(X)$ to have a common factor. But $f'(X)=(X+1)^{p-1}-X^{p-1}$. If $r$ is some real such that $f'(r)=0=f(r)$, then we have $(r+1)^p-r^p-1=0$ and $(r+1)^{p-1}=r^{p-1}$. Multiplying the second equation by $(r+1)$ gives $r^p+1=(r+1)^p = r^p+r^{p-1}$. Thus $r^{p-1}=1$. Therefore, $(r+1)^{p-1}=1$. In order to have both equations satisfied, $r$ and $r+1$ should be roots of unity. Note taking $r=e^{2i\pi/3}$ works. This suggests that $3\mid p-1$ with our factor $a(X)$ being $X^2+X+1$, and we can check that $a(X)^2\mid f(X)$ when $3\mid p-1$. Moreover, we can find some residue $s$ such that $p\mid a(s)$. It follows that $p^2\mid f(s)$, or $p^3\mid (s+1)^p-s^p-1$.

The exact lemma to prove this was one of Gabriel's (Zimbabwe?) problems in last year's NT3 class. In fact, I believe the problem was: Gabriel wrote: If $a,b$ are positive integers and $p$ a prime such that $p\mid a^2+ab+b^2$, then prove that $p^3\mid (a+b)^p-a^p-b^p$. Unfortunately, the intersection of those who took NT3 and those who made TST is the null set, probably.

So on the test, I factored the polynomial (with $b=1$) for $n=7$ as $7a(a+1)(a^4+2a^3+3a^2+2a+1)$, but then forgot to actually factor this further. I also observed that there would probably only be solutions when $p\equiv 1 \pmod{3}$ (as there's no other reason that 7 would work while 5 and 11 don't) but apparently primitive cube roots don't mean anything to me. I also never thought not paying much attention to the WOOT message board would bite me in the butt so much.

We will prove that for each prime $p$, there exist $x$ such that $(x+1)^p-x-1$ is divisible by $p^3$. Lemma: Let $P(x)$ be a nonconstant polynomial with integer coefficients and $p$ be a prime number. Then if $P(x)\equiv 0 \pmod p$ is solvable , then $P(x)\equiv 0 \pmod {p^n}$ is solvable too , for each $n\in N$. Proof. By induction Let $P(x_0)\equiv 0 \pmod {p^{n-1}}$. Then taking $x=x_0+p^{n-1}t$ and using Taylor's formula we see that we can find such suitable $t$. Now in problem since $P(x)=(x+1)^p-x-1$ then by Fermat theorem $P(x)\equiv 0 \pmod p$ is solvable, then by lemma $P(x)\equiv 0 \pmod {p^3}$ is solvable too.

Sorry,my solution is wrong. i miss the condition $x<p$

CantonMathGuy wrote: Some links with spoilers killing this problem: http://artofproblemsolving.com/community/c194913h1319556 (for people in WOOT) http://math.stackexchange.com/questions/1961526 (linked to in the WOOT post) http://kvant.mccme.ru/pdf/2010/2010-02.pdf Page 28

Why was this easier than both 1 and 2?

Shaddoll wrote: Why was this easier than both 1 and 2? v_Enhance wrote: This problem was on TST because it was test-solved by (at least) nine different graders and instructors, including me. Less than half of them solved it, and in particular I spent five hours on the problem and was not able to find a solution. The problem was generally positively received and none of the graders reported having seen it before. ... For me, the trigger should have been the solution to ELMO 2009/6. The problem actually crossed my mind while I was test-solving, but I didn't make the connection. Granted, I had been working at a noisy conference, and maybe would have found it on a better day (or maybe I'm just deluding myself ). Fine if you can guess the roots of unity quickly. I probably should have since I also did $p=7$, but apparently I'm too old to recognize how $X^4+2X^3+3X^2+2X+1$ factors even when it's staring me in the face.

Shaddoll wrote: Why was this easier than both 1 and 2?

I didnt undestand lemma 1.

Hmm really easy for a TST 3. CantonMathGuy wrote: Prove that there are infinitely many triples $(a, b, p)$ of positive integers with $p$ prime, $a < p$, and $b < p$, such that $(a + b)^p - a^p - b^p$ is a multiple of $p^3$. Noam Elkies Take any $p \equiv 1 \pmod{6},$ and we claim that there would exist $(a,b)$ such that $(a,b,p)$ works. Indeed, consider $f(X) \overset{\text{def}}{=}(X+b)^p-X^p-b^p$ for any $0<b<p.$ Then $$f(b\omega)=b^p(\omega+1)^p-b^p-b^p\omega^p=-b^p(1+\omega^p+\omega^{2p})=0.$$Further, $$f'(b\omega)=p(b\omega+b)^{p-1}-p(b\omega)^{p-1}=pb^{p-1}\omega^{2(p-1)}-pb^{p-1}\omega^{p-1}=0$$since $3 \mid p-1.$ So $b\omega$ is a double root of $f.$ This means $$(a^2+ab+b^2)^2 \mid (a+b)^p-a^p-b^p \qquad \text{for all }a,b.$$Clearly $p \mid f(a).$ Also, by Thue there exists $a,b$ such that $p=a^2+ab+b^2$ so $p^3 \mid f(a),$ so done. $\square$

Very similar to an old IMO problem which asked 1 solution for 7^7 dividing the expression with p=7

https://mathoverflow.net/a/255935 Amazing.

Is this legitimate? The key claim is motivated from small cases. Choose $p\equiv 1\pmod{3},$ and let $f(a,b)=(a+b)^p-a^p-b^p.$ $\textbf{Key Claim: }$ $(a^2+ab+b^2)^2\mid f(a,b)$ $\emph{Proof: }$ Fix $b,$ and treat $f$ as a polynomial in $a.$ The roots of $a^2+ab+b^2$ are $a=b\omega$ for a cubic root of unity $\omega,$ so it suffices to verify that $f(b\omega)=f'(b\omega)=0.$ Note that $(\omega+1)^3=3(\omega^2+\omega+1)-1=-1,$ so \begin{align*} f(b\omega) &=(b\omega+b)^p-(b\omega)^p-b^p\\ &= b^p((\omega+1)^p-\omega^p-1)\\ &= b^p(\omega+1-\omega-1)\\ &= 0. \end{align*}Similarly, we have $f'(a)=p(a+b)^{p-1}-pa^{p-1},$ so \begin{align*} f'(b\omega) &= p(b\omega+b)^{p-1}-p(b\omega)^{p-1}\\ &= pb^{p-1}((\omega+1)^{p-1}-\omega^{p-1})\\ &= pb^{p-1}((-1)^{(p-1)/3}-1)\\ &= 0. \end{align*}Therefore, $a=b\omega$ is a double root of $f,$ as needed. $\blacksquare$ $\textbf{Claim: }$ There exist $0<a,b<p$ satisfying $p^2\mid a^2+ab+b^2$ $\emph{Proof: }$ Let $g$ be a primitive root mod $p^2.$ Since $\varphi(p^2)=p^2-p\equiv 0\pmod{3},$ the set $\{g^3,g^6,\dots,g^{3\varphi(p^2)}\}$ cannnot span all (not divisible by $p$) residues mod $p^2.$ Hence, the cubes are not surjective mod $p^2,$ so there exist distinct mod-$p^2$ residues $a,b$ such that $a^3-b^3\equiv 0\pmod{p^2}.$ Furthermore, we cannot have $a\equiv b\pmod{p};$ if we do, then expansion yields $3kpa^2\equiv 0\pmod{p^2},$ contradiction. Thus, we must have $a^2+ab+b^2\equiv 0\pmod{p^2},$ as desired. $\blacksquare$ Finally, note that (by expansion), $p\mid f(a,b),$ clearly giving $p^5\mid f(a,b).$ We have shown that a triple satisfying the problem statement exists for all $p\equiv 1\pmod{3},$ so we are done.

The main claim is as follows: Claim: For $p \equiv 1\pmod 3$, the polynomial $x^2 + x + 1$ divides $(x + 1)^p - 1^p - x^p$ with multiplicity at least $2$. We extend this division statement to the complex numbers. Obviously $x = 1$ works; now set $x = \omega$ where $\omega$ is a third root of unity. We see that \begin{align*} (\omega + 1)^p - 1 - \omega^p &= (-\omega^2)^p - \omega^p - 1 \\ &= -\omega^2 - \omega - 1 = 0, \end{align*}as desired. We do a similar calculation to show that $\omega^2$ works as well. Thus $x^2 + x + 1$ divides $(x + 1)^p - x^p - 1$ with multiplicity at least one. To get the next division, we take the derivative to get the new polynomial $p(x + 1)^{p - 1} - px^{p - 1}$. We can check once again that \begin{align*} p(\omega + 1)^{p - 1} - p\omega^{p - 1} = p - p = 0, \end{align*}since $p - 1 \equiv 0\pmod 3$. As a result, $1, \omega, \omega^2$ are all double roots of $(x + 1)^p - x^p - 1$, proving the claim. $\square$ Since $\binom{p}{1}, \binom{p}{2}, \cdots, \binom{p}{p - 1}$ all contain a factor of $p$, we see that we can write \begin{align*} (a + b)^p - a^p - b^p = p(a^2 + ab + b^2)^2 \cdot Q(a, b). \end{align*}Now selecting $a, b$ such that $x = ab^{-1}$ and $x^2 + x + 1 \equiv 0\pmod p$ finishes by taking $x$ to be $g^{\frac{p - 1}{3}}$, where $g$ is a primitive root of unity.

CantonMathGuy wrote: Prove that there are infinitely many triples $(a, b, p)$ of positive integers with $p$ prime, $a < p$, and $b < p$, such that $(a + b)^p - a^p - b^p$ is a multiple of $p^3$. Noam Elkies Pretty easy for a P6. Solved with MathLuis. First of all, for every prime \(p\equiv1\pmod{3}\), there exists an integer \(x\) for which \(p\mid x^2+x+1\). Motivated by this, we will try to show that the proposed statement works for all primes \(1\pmod{3}\). Now, we will show that \(x^2+x+1\mid f'(x)\) where \(f(x)=(x+1)^p-x^p-1\), then we will have showed that \((x^2+x+1)^2\mid f(x)\) (since \(x^2+x+1\mid f(x)\) by root of unity). This can be done because \[f'(x)=p[(x+1)^{p-1}-x^{p-1}]\]and since \(3\mid p-1\), \(x^{p-1}\equiv1\pmod{x^2+x+1}\), and so we need to show that \(x^2+x+1\mid (x+1)^{p-1}-1\) which is true because you choose \(x\) as the cube root of unity and see that \((\omega+1)^3=1\) so we have showed that \((x^2+x+1)^2\mid f(x)\). Now, for polynomials \(A\) and \(B\) with integral coefficients, if \(g\mid A\) for all \(A\) and \(B\mid A\), then \(B\mid\frac{A}{g}\), so \(gB\mid A\). With this argument and Lagrange's theorem, we have that \[p(x^2+x+1)^2\mid f(x)\]because \(p\mid(x+1)^p-x^p-1\) by Lagrange and since \(p\mid x^2+x+1\), we have that \[p^3\mid p(x^2+x+1)^2\mid f(x)\]and we are done, because for all primes \(p\equiv1\pmod{3}\), choose \(a=x\) and \(b=1\), where \(p\mid x^2+x+1\).

actual memes Let's only consider primes $p \equiv 1 \pmod 3$. The following observations about such primes solves the problem: Claim: The two-var polynomial $p(a^2 + ab + b^2)^2$ divides the two-var polynomial $(a + b)^p - a^p - b^p$. Proof: It is sufficient to prove that the 1-var polynomial $p(a^2 + ab + b^2)^2$ in terms of $a$ divides the 1-var polynomial $(a + b)^p - a^p - b^p$ in terms of $a$ across all complex constants $b$. Clearly $p \mid (a + b)^p - a^p - b^p$ since\[(a + b)^p - a^p - b^p = \sum_{i = 0}^p \binom{p}{i}a^ib^{p - i} - (a^p + b^p) = \sum_{i = 1}^{p-1} \binom{p}{i}a^ib^{p - i}\]and it is easy to see $p$ divides all binomial coefficients $\tbinom{p}{i}$ for $i \neq 0, p$. Now, to show $P(a) = (a^2 + ba + b^2)^2$ divides $Q(a) = (a + b)^p - a^p - b^p$, we must show that the roots of $P(a)$ are double roots of $Q(a)$, so it suffices to show the roots of $P(a)$ are the roots of both $Q(a)$ and $Q'(a)$. The roots of $P(a)$ are $b\omega$ and $b\omega^2$ where $\omega = e^{\frac{2\pi i}{3}}$. Check \begin{align*} Q(b\omega) & = b^p[(1 + \omega)^p - \omega^p - 1]\\&= b^p[-\omega^{2p} - \omega^p - 1]\\&=b^p[-\omega^2 - \omega^p - 1]\\&=0 \end{align*}\begin{align*} Q(b\omega^2) & = b^p[(1 + \omega^2)^p - \omega^{2p} - 1]\\&= b^p[-\omega^{p} - \omega^{2p} - 1]\\&=b^p[-\omega^p - \omega^{2p} - 1]\\&=0 \end{align*}and that since $Q'(a) = p[(a + b)^{p-1} - a^{p-1}]$, check \begin{align*} Q'(b\omega) & = pb^{p-1}[(1 + \omega)^{p-1} - \omega^{p-1}]\\&=0 \end{align*}\begin{align*} Q'(b\omega^2) & = pb^{p-1}[(1 + \omega^2)^{p-1} - \omega^{2(p-1)}]\\&=0 \end{align*}since $3 \mid p-1$, so $w^{p-1} = 0$. This check finishes the proof of this claim. Claim: If prime $p \equiv 1 \pmod 3$, then there exist residues $a, b$ for which $p \mid a^2 + ab + b^2$. Proof: This is equivalent to proving there exist distinct residues $a, b$ for which $a^3 \equiv b^3 \pmod p$ since $p \nmid a - b$. Let $g$ be a primitive root, and say $g^1, g^2, \ldots , g^{p-1}$ generates all $p-1$ nonzero residues. We can literally select\[(a, b) = \left(g^i, g^{i + (p-1)/3}\right)\]and be done (which is legal due to $3 \mid p - 1$). So now to kill the problem, just choose $p \equiv 1 \pmod 3$ and distinct residues $a, b$ modulo $p$ for which $a^3 \equiv b^3 \pmod p$, of which there are clearly infinitely many triples.

The key claim is that if $p \equiv 1 \pmod{6}$, then $(a^2+ab+b^2)^2 \mid (a+b)^p-a^p-b^p$ (in the polynomial sense). First we show that $a^2+ab+b^2 \mid (a+b)^p-a^p-b^p$. Divide through by $b$ and let $a/b=x$, so the condition becomes $x^2+x+1 \mid (x+1)^p-x^p-1$. Viewing this in $\mathbb{C}$, we can plug in $x=e^{2\pi i/3},e^{4\pi i/3}$, which are the roots of the LHS, and the conclusion follows from $p \equiv 1 \pmod{6}$. To prove that $e^{2\pi i/3}$ and $e^{4\pi i/3}$ are double roots, we take the derivative of the RHS, which is $p((x+1)^{p-1}-x^{p-1})$. Since $6 \mid p-1$ and $e^{2\pi i/3}+1,e^{4\pi i/3}+1$ are both sixth roots of unity, it follows that $e^{2\pi i/3},e^{4\pi i/3}$ divide the derivative as well, hence they are double roots and $(x^2+x+1)^2 \mid (x+1)^p-x^p-1$ follows. To finish, pick some $p \equiv 1 \pmod{6}$, of which there are infinitely many by Dirichlet. Since $3 \nmid p-1$, there exists some solution $x=k<p$ to $x^2+x+1 \equiv 0 \pmod{p}$. Then because $(k+1)^p-k^p-1^p$ is an integer polynomial with coefficients all divisible by $p$, and $p^2 \mid (k^2+k+1)^2 \mid (k+1)^p-k^p-1^p$, it follows that $p^3 \mid (k+1)^p-k^p-1^p$, as desired. $\blacksquare$

Literal $5$ mohs problem, this took me less time than P1 on this test... Claim: For $p \equiv 1 \pmod 6$, simply taking $a = 1, b = \omega$ where $b$ is a nontrivial cube root of unity suffices. Proof: $(1+x+x^2)^2 \mid (1+x)^p - 1 - x^p$ since $(1+\omega)^p - 1 - \omega^p = 1+ \omega - 1 - \omega = 0$ and $p(1+\omega)^{p-1} - p(\omega)^{p-1} = p - p = 0$. So we are done since $p \mid (1+x)^p - 1 - x^p$. EDIT: Basically identical to 2022 ELMO P2. No wonder.

I'm going to actually prove the claim that we can choose $p^2 = x^2 + xy + y^2$ for positive integers $x$ and $y$. $\textbf{Claim.}$ Let $p$ be a prime that is $1$ mod $3$. Then there exist positive integers $x$ and $y$ such that \[ x^2 + xy + y^2 = p. \]$\emph{Proof.}$ To see this, consider the lattice spanned by \[ m(a, 1) + n(p,0) \]where $0 \le a < p$ and $a^2 + a + 1 \equiv 0 \pmod{p}$. $a$ exists by condition. Consider the set of points $(x,y)$ such that $x^2 + xy + y^2 < 2p$. This is an ellipse, and is hence convex. Moreover note that it is symmetric about the origin. Computing the area, we set $y=x$ and $y=-x$ as it is tilted $45$ degrees, and find that the area of this region is \[ \frac{4p \pi}{3}. \]But then note that the area of the fundamental parallelogram of the lattice is \[ \Delta = \det \begin{bmatrix} a & p \\ 1 & 0 \end{bmatrix} = p, \]and since $\pi > 3$, we have \[ \frac{4p \pi}{3} > 4p = 4\Delta,\]whereby using Minkowski's theorem, we must have a lattice point $(u,v)$ which is not $(0,0)$ inside this convex set. Now, \[ (ma + p)^2 + (ma + p)(m) + m^2 \equiv m^2(a^2 + a + 1) \equiv 0 \pmod{p}, \]so $p \mid u^2 + uv + v^2$. In particular, since $0 < u^2 + uv + v^2 < 2p$, we find that $u^2 + uv + v^2 = p$. Now suppose $u < 0$ and $v > 0$, and $|u| \ge v$. Then observe the equality \[ u^2 + uv + v^2 = v^2 + v(-u-v) + (-u-v)^2 \]and note that $-u-v \ge 0$ because $-u \ge v$. In any case we have a solution in nonnegative integers, and we can't have a solution that has $0$ for one of the variables, as otherwise $p$ is a square. Bad. $\square$ Particularly, note the identity \[ (a^2 + ab + b^2)(a^2 + ab + b^2) = (a^2 - b^2)^2 + (a^2 - b^2)(b^2 + 2ab) + (b^2 + 2ab)^2. \]If we let $a > b$ be a solution to $a^2 + ab + b^2 = p$, then we have \[ p^2 = x^2 + xy + y^2 \]for positive integers $x$ and $y$. It then follows that $0 < x, y < p$. Anyway, now for the actual problem! Now let $p \equiv 1 \pmod{3}$ be a prime. Observe that $p$ is hence $1$ mod $6$. Also note the polynomial \[ (x + 1)^p - x^p - 1 \]takes $\zeta^2 = e^{\frac{2\pi i}{6}}$ as a root, and differentiating, one finds \[ \zeta^{p-1}- \zeta^{2p-2} = 1 - 1 = 0 \]and so we have a double root. In particular, for these primes, \[ (x^2 + x + 1)^2 \mid (x + 1)^p - x^p - 1.\] As such, combined with the fact that $p$ just divides the polynomial, \[ p(a^2 + ab + b^2)^2 \mid (a + b)^p - a^p - b^p.\]Setting the desired $x$ and $y$ gets the result.

kind of bummed Fix $p \equiv 1 \pmod{3}$. We show that $p(a^2+ab+b^2)^2 \mid (a+b)^p - a^p - b^p$ as polynomials. Indeed, it suffices to show that $p(x^2 + x + 1)^2 \mid (x+1)^p - x^p - 1$. Clearly by FLT $p \mid (x+1)^p - x^p - 1$. Let $\omega = e^{\frac{2 \pi i}{3}}$ and let $P(x) = (x+1)^p - x^p - 1$. It suffices to check that $P(\omega) = P'(\omega) = 0$. Indeed, we have (since $\omega^2 = \omega + 1$) that $P(\omega) = -\omega^2 - \omega - 1 = 0$ and $P'(\omega) = p(\omega + 1)^{p-1} - p\omega^{p-1} = 0$. To finish, by Thue's lemma there exists a pair $(a, b)$ with $p^2 = a^2 + ab + b^2$, done (and in fact we have shown the stronger claim that $p^5 \mid (a+b)^p - a^p - b^p$).

rightways wrote: We will prove that for each prime $p$, there exist $x$ such that $(x+1)^p-x-1$ is divisible by $p^3$. Lemma: Let $P(x)$ be a nonconstant polynomial with integer coefficients and $p$ be a prime number. Then if $P(x)\equiv 0 \pmod p$ is solvable , then $P(x)\equiv 0 \pmod {p^n}$ is solvable too , for each $n\in N$. Proof. By induction Let $P(x_0)\equiv 0 \pmod {p^{n-1}}$. Then taking $x=x_0+p^{n-1}t$ and using Taylor's formula we see that we can find such suitable $t$. Now in problem since $P(x)=(x+1)^p-x-1$ then by Fermat theorem $P(x)\equiv 0 \pmod p$ is solvable, then by lemma $P(x)\equiv 0 \pmod {p^3}$ is solvable too. It doesnt work for $x squared + 1 $

We prove a stronger result, with $p^3$ replaced by $p^5$. I claim that, in particular, if we pick $p \equiv 1 \pmod 3$, there will always exist $(a, b)$ which satisfy the condition; this solves the problem by Dirichlet. Claim. $(a^2+ab+b^2)^2 (a+b) \mid (a+b)^p - a^p - b^p$ for these $p$. Proof. Computation. Note that setting $b = a\omega$ where $\omega^3 = 1$, $$(1+\omega)^p - 1 - \omega^p \equiv 1+\omega - 1 - \omega \equiv 0 \pmod p.$$Further, upon taking a derivative and de-homogenizing, we can check that $$f'(x) = p(1+x)^{p-1} - 1 - px^{p-1}$$satisfies $f'(\omega) = 0$ too. $\blacksquare$ Now notice that $a^2+ab+b^2 \equiv 0 \pmod p$ always has a solution when $p \equiv 1 \pmod 3$ (equivalently, $-3$ is a QR mod $p$), so this shows $p^3$. To extend this to $p^5$, we will show that $a^2+ab+b^2 \equiv 0 \pmod {p^2}$ has a solution with $a, b < p$ too. Notice that by homogenization all solutions $(a, b)$ satisfy $a = |kb|$ for some $k^2+k+1 \equiv 0 \pmod {p^2}$, so it really suffices to show the following: [Sidenote: we can drop the $a<b$ condition WLOG here because otherwise just take $k^{-1}$ instead.] Claim. For any $k$, there exist $|a|, |b| < p$ such that $a \equiv kb \pmod {p^2}$. Proof. This succumbs to a tricky Pigeonhole argument: there are $p^2$ pairs of the form $a - kb$ where $0 < a, b < p$, but there are only $p^2-1$ values this can attain modulo $p^2$. Hence we have $$a_1-kb_1 \equiv a_2-kb_2 \iff a_1 - a_2 \equiv k(b_1-b_2) \pmod {p^2}.$$Note that $|a_1-a_2|, |b_1-b_2| < p$, thus done. $\blacksquare$

I shall sketch my solution( as it is the same as all of the above). But I will also write remarks containing motivation.