prove by induction that $29^n - 21^n$ is always divisible by $8$

Question

I have to prove by induction that that $\forall n \in N,$ $8 | (29^n - 21^n) $ . I understand how to prove things with induction generally, but im not sure where to even start with this one. I have the base cases $\frac{29^0 - 21^0}{8} = 0$ and $\frac{29^1 - 21^1}{8} = 1$ but I am lost after that.

Answer 1

For $n=1$ it is obviously true. Assume that it is true for $n \in \mathbb N$ then for $n+1$ you have that $$29^{n+1}-21^{n+1}=29^n\cdot29-21^n\cdot21=(29^n-21^n)\cdot21+29^n\cdot8$$ but by induction hypothesis $$8 \mid 29^n-21^n$$ and trivially $8 \mid 29^n\cdot 8$. Combining these two $$8 \mid \left((29^n-21^n)\cdot21+29^n\cdot8\right)$$ which completes the proof.

---

You can generalize this proof for $A>B$ two positive integers such that $$A-B=k$$ where $k$ is again a positive integer to obtain that $$k \mid (A^n-B^n)$$ Here $A=29, B=21$ and $k=8$.

Answer 2

Recall the identity $$(a^n - b^n)(a + b) = a^{n+1} - b^{n+1} + ab(a^{n-1} - b^{n-1}).$$ Now define $d_n = a^n - b^n$; then $$d_{n+1} = (a+b)d_n - ab d_{n-1}.$$ It follows by induction that for any positive integer $m$, if $m \mid a-b$, then $m \mid d_n$ for all positive integers $n$, since $d_0 = 0$ is trivially divisible by $m$.

Answer 3

By the binomial theorem, $ 29^n= (21+8)^n = 21^n + 8a. $