0
$\begingroup$

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.

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

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$.

$\endgroup$
2
$\begingroup$

${\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.