Find all pairs $(a,n) \in \Bbb N^2$ that $n|(a+1)^n-a^n$ Find all $(a,n) \in \Bbb N^2$ Such that
$$n\mid (a+1)^n-a^n$$
Denote the solution set by $S$
I have tried to proceed a bit and have shown the following


*

*Trivially True for $n=1$, i.e., $\Bbb N\times\{1\}$ is a subset of $S$.

*Never possible if $n$ is a prime.

*if $n>1$, and $n$ divides either $a$ or $a+1$, this is not possible.


Are there other possibilities?
 A: We claim that the only pairs $(a,n)\in \Bbb Z\times\Bbb N$ s.t. $n\mid(a+1)^n-a^n$ come from the case $n=1$.  We prove by contradiction.
Let $n>1$ be the smallest possible positive integer such that there exists $a\in \mathbb{Z}$ for which $(a+1)^n\equiv a^n\pmod{n}$.  Clearly, this implies $\gcd(a,n)=\gcd(a+1,n)=1$.  Let $t$ denote $(a+1)a^{-1}$ modulo $n$.  Then $t^n\equiv 1\pmod{n}$.  Furthermore we know by Euler's theorem that $t^{\phi(n)}\equiv1\pmod{n}$.  Thus, $t^d\equiv 1\pmod{n}$ where $d=\gcd\big(n,\phi(n)\big)$.  If $d\ne 1$, then we see that $d<n$ (as $\phi(n)<n$ for all $n>1$) and $$(a+1)^d\equiv t^da^d\equiv 1\cdot a^d\equiv a^d\pmod{d},$$
but this contradicts the assumption that $n$ is the smallest integer $>1$ that works.  Hence $d=1$.  But this means $t\equiv 1\pmod{n}$, which makes $$a+1\equiv ta\equiv a\pmod{n}$$ 
or $n\mid 1$, which is absurd.
A: *

*Trivial;

*If $n=p$ prime then you have that $x\mapsto x^p$ is a morphism of $\mathbb{Z}/p\mathbb{Z}$, so 
$(a+1)^p\equiv a^p+1^p\equiv a^p+1  $mod $p$
Thus 
$(a+1)^p-a^p\equiv 1$ mod $p$
By contradiction if $p|(a+1)^p-a^p$ then 
$(a+1)^p-a^p\equiv 0$ mod $p$ so we would have 
$0\equiv 1$ mod $p$ that is not possible;


*It is not possible because $a+1$ and $a$ are coprime, so if $n|a+1$ and $n| a$ we must have $n=1$ while $n>1$
We study the case $n=4$:
In this case
$(a+1)^4-a^4\equiv a^4+2a^2+1-a^4\equiv 2a^2+1$ mod $4$
But $2a^2+1$ is an odd number, so it can not be equal to $0$ mod $4$.
This means that $(a,4)$ it does not belong  to your set. 
This idea can be generalized for the case $n=2k$ even, in fact you can  observe that 
$n| \binom{n}{c}$ for each $c\neq k$ and $n\neg | \binom{2k}{k}$, thus you have that 
$(a+1)^n-a^n\equiv a^n +\binom{2k}{k}a^k +1-a^n$
$ \equiv \binom{2k}{k}a^k +1$ mod $n$
However, $ \binom{2k}{k}a^k +1$ is odd, so it is not congruent to $0$ module $2k$
This means that $(a,2k)$ does not  belong to your set.
