# How can I show that this is an integer for all positive integers $a$ and $n$?

How do I prove that this is an integer for all positive integers $a$ and $n$?

$$\frac {(a+1)^n - (a+1)}{a}$$

I was thinking of somehow eliminating the fraction but I'm not sure how.

• Hint: Binomial theorem. Or factor $x^n-x$. – Michael Burr Nov 15 '16 at 2:42
• Factor out $(a+1)$ and then use the fact that $y^k-1 = (y-1)(y^{k-1}+y^{k-2}+\cdots+1)$. – Isko10986 Nov 15 '16 at 2:43

## 2 Answers

Notice that $$(a+1)^1 = a+1\\ (a+1)^2 = a^2 + 2a + 1\\ (a+1)^3 = a^3 + 3a^2 + 3a + 1\\ (a+1)^4 = a^4 + 4a^3 + 6a^2 + 4a + 1$$ and so on.

The last two terms are always $na + 1$. After subtracting $a+1$ from the polynomial, the remaining terms are all divisible by $a$.

{\rm mod}\,\ a\!:\:\ \color{#c00}{a\equiv 0}\ \ \Rightarrow\ \ \begin{align}&(\color{#c00}a+1)^n-(\color{#c00}a+1)\\ \equiv\ &(\color{#c00}0+1)^n-(\color{#c00}0+1)\\ \equiv\ &\qquad\ 1^n-1\ \equiv\ 0\end{align}\ \

using standard Congruence Arithmetic Rules.