Binomial theorem: divisibility by $n^2$ Consider $X = (a+b)^n-a^n-b^n$  where

*

*$a$ and $b$ and $a+b$ are not divisible by $n$,

*$n>=3$ is positive and prime,

*$a \ne b$ and both are greater than 1.

By the binomial expansion we know $X$ is divisible by $n$, but how can we study whether $X$ is divisible by $n^2$ or other powers of $n$?
Specifically I am interested to prove $X$ is NOT divisible by $n^2$, but I am not sure how to prove or disprove it.
 A: Julian Rosen figured it out in the comments. I'm just going to explain what's going on in the OEIS and the linked website, which is Kevin Brown's.
You can eliminate one of the variables by
$$(a+b)^n-a^n-b^n\equiv 0 \mod n^2$$
$$b^{-n}(a+b)^n-b^{-n}a^n-1\equiv 0$$
Now let $x\equiv ab^{-1}$
$$(x+1)^n-x^n-1\equiv 0$$
It's easy to check by expanding the binomial that if $x\equiv y\mod n$ then  $(x+1)^n-x^n-1\equiv (y+1)^n-y^n-1\mod n^2$, so I'm just going to look at $x\equiv 0,1,2\dots n-1$.
This has trivial solutions when $x\equiv 0,-1\mod n$.
Now I'll prove that if $n\equiv 1\mod 6$ then there are other solutions. $(x+1)^n-x^n-1$ is a multiple of $x^2+x+1$. This follows from the fact that the roots of the second are also roots of the first:
$$x^2+x+1=0\implies x=\frac{-1\pm \sqrt{-3}}2$$
These are cubic roots of unity, plus $x+1=\frac{1\pm \sqrt{-3}}2$ are sixth roots of unity. Since all primes greater than 3 are $\pm 1 \mod 6$ it suffices to prove it for $n=5,7$ and the other cases follow by reducing mod 6.
The equation:
$$x^2+x+1\equiv 0\mod n$$
Is solvable when $-3$ is a quadratic residue mod n.
$$(2x+1)^2\equiv -3$$
Which in turn happens when $n\equiv 1 \mod 6$. So the only cases that may not have solutions are $n\equiv -1$. A few of them do though, as listed on OEIS the first being 59. So your question is hard, probably has no known solution and isn't solvable by elementary methods.
Furthermore, if $x$ is a solution to the equation then so are $x^{-1}$ and $-1-x$. You can compose those and find $-1-x^{-1}$ and $(-1-x)^{-1}$ and so on until you find that they wrap around getting you at most 6 solutions. The times when you don't get 6 are: the trivial solutions $0,-1$, the pair of solutions of $x^2+x+1\equiv 0$, and the trio $1,-2,-2^{-1}$. Morgan Rodgers proves this for me here. That last trio of solutions occur when
$$2^n\equiv 2 \mod n^2$$
Which is the definition of a Wieferich prime.
