Mathematical Induction and Divisibility $7\mid 11^n-4^n$ Prove $11^{n} - 4^{n}$ is divisible by 7 for all natural numbers n.
I know this holds for the base case of n = 1. Am I supposed to use $11^{n + 1} - 4^{n + 1}$ for the induction step?
Any help would be greatly appreciated!
Thank you in advance!
 A: We have that $11\equiv 4 \pmod{7}.$ Thus 
$11^n\equiv 4^n \pmod{7}, \forall n\in\mathbb{N}.$ That is, $11^n-4^n$ is divisible by $7.$
If you want to use induction note that
$$11^{n+1}-4^{n+1}=(7+4)\cdot11^n-4\cdot4^n=7\cdot 11^n+4\cdot(11^n-4^n).$$ Now $7\cdot 11^n$ and $11^n-4^n$ are multiples of $7$ (the second one using the induction hypothesis).
A: Without induction: $11^n-4^n=(11-4)(11^{n-1}+11^{n-2}\cdot 4 + \cdots + 4^{n-1})$ where $11-4=7$.
A: Instead of induction, write $11^n$ as $(7+4)^n$ and expand using the binomial theorem. After you subtract away the $4^n$ term, every remaining term has at least one factor of $7$.
A: If you have proved the base case, now move on to the induction step.
Assume $n=k$, and that $7|(11^k - 4^k)$. This means that $11^k - 4^k = 7M$
Now prove your induction step.
So that: $7|(11^k - 4^k) \to 7|(11^{k+1} - 4^{k+1})$
A: First, show that this is true for $n=1$:
$11^{1}-4^{1}=7$
Second, assume that this is true for $n$:
$11^{n}-4^{n}=7k$
Third, prove that this is true for $n+1$:
$11^{n+1}-4^{n+1}=$
$11(11^{n})-\color\green{4}(4^{n})=$
$11(11^{n})-(\color\green{11-7})(4^{n})=$
$11(11^{n})-11(4^{n})+7(4^{n})=$
$11(\color\red{11^{n}-4^{n}})+7(4^{n})=$
$11(\color\red{7k})+7(4^{n})=$
$7(11k)+7(4^{n})=$
$7(11k+4^{n})$

Please note that the assumption is used only in the part marked red.
A: Another way to to do it without induction is to note that the mod cycles for powers of $11$ and $4$ modulo congruent to $7$ correspond to each other. 
$$\begin{equation}\begin{aligned}11 &\equiv 4 \pmod 7\\ 11^2 &\equiv 2 \pmod 7\\ 11^3 &\equiv 1 \pmod 7 \\ 11^4 &\equiv 4 \pmod 7 \\ &\vdots\end{aligned}\end{equation}$$
$$\begin{equation}\begin{aligned}4 &\equiv 4 \pmod 7\\ 4^2 &\equiv 2 \pmod 7\\ 4^3 &\equiv 1 \pmod 7 \\ 4^4 &\equiv 4 \pmod 7 \\ &\vdots\end{aligned}\end{equation}$$
So for any $n$, $11^n \equiv 4^n \equiv r \pmod 7$, so $11^n - 4^n \equiv r - r \pmod 7 \implies 11^n - 4^n \equiv 0 \pmod 7$ as desired. 
