Prove that $p$ divides $(n+1)^p - n^p - 1$

Question

for $p \in \mathbb{P},\space n \in \mathbb{N}$.

Farthest I've gotten so far is $\sum\limits_{k=1}^{p-1}\frac{(p-1)!\space n^k}{k!\space (p-k)!}$ but I don't see how the fraction is supposed to be an integer.

Answer 1

Since $p$ is prime there are no factors of $p$ in any natural numbers less than $p$. So ${p \choose k} = \frac {p!}{k!(p-k)} = p*\frac {(p-1)!}{k!(p-k)!}$ is divisible by $p$ (as $\gcd(p, k!(p-k)!) = 1$).

[This won't necessarily be the case if $p$ is not prime. $\gcd(s, k!(s-k)!)$ need not be $1$ so ${s \choose k}= \frac {s!}{k!(s-k)!}$ is an integer but $s*\frac {(s-1)!}{k!(s-k)!}$ need not be divisible by $s$.]

So $(n + 1)^p = n^p + \sum_{k=1}^{p-1} {p\choose k}n^k + 1 - n^p - 1= \sum_{k=1}^{p-1} {p\choose k}n^k$ and each term ${p\choose k}$ is an integer divisible by $p$.

Method 2: With Fermat's little thereom either $p|n+1$, in which case $p|(n+1)^p - (n+1)$, or $\gcd(n+1, p) = 1$ so $(n+1)^p \equiv n+1$ and so $(n+1)^p - n-1 \equiv (n+1) -(n+1) \equiv 0 \mod p$. So $p|(n+1)^p - n - 1$.

Answer 2

Since you seem to be looking at binomial expansion anyways, just notice that

$$(n + 1)^p = \sum_{k = 0}^p \binom{p}{k} n^p.$$

Now the terms with $k = p$ and $k = 0$ cancel because of the subtraction, and it's a useful fact that for all $0 < k < p$, the binomial coefficient $\binom{p}{k}$ is divisible by $p$.

Answer 3

Since $p$ is a prime number Fermat's little theorem says that $p$ divides both $(n+1)^p-(n+1)$ and $n^p-n$. Therefore, $p$ divides their difference, which is $$(n+1)^p-(n+1)-n^p+n=(n+1)^p-n^p-1$$

Answer 4

Each number $\dfrac{(p-1)!}{k!(p-k)!}$ is an integer. In fact, since:

• $\displaystyle\frac{p!}{k!(p-k)!}=\binom pk$ is an integer and therefore $k!(p-k)!\mid p!=(p-1)!\times p$;
• $\displaystyle\gcd\bigl(p,k!(p-k)!\bigr)=1$,

$k!(p-k)!\mid(p-1)!$. In other words, $\dfrac{(p-1)!}{k!(p-k)!}$ is an integer.

Answer 5

by FLT

$$(n+1)^p - n^p - 1\equiv (n+1)-n-1\equiv0 \mod p$$

Answer 6

If you expand the bracket binomial then you can find that n^p and 1 will cancel out by putting k=1 and k=p . The rest terms will contain p or higher powers of p which is divisible by p. Alternatively you can go for FLT.

Answer 7

$$(1+n)^p = \sum_{k=0}^P \binom pkn^k$$

For any $k$ such that $0 < k < n$

$$\displaystyle \binom pk = \dfrac{p!}{k!(p-k)!} = \begin{array}{c} p & (p-1) & (p-2) & \cdots & (p-k+1) \\ \hline k & (k-1) & (k-2) & \cdots & 1 \\ \end{array}$$

Note there is a factor of $p$ in the numerator and that all of the factors in the denominator are less than $p$. Hence, for $0 < k < p, \quad$ $\displaystyle p \left| \binom pk \right.$