<s>[INST] Prove that $7 \mid 11^n - 4^n$ with mathematical induction I want to prove that $7 \mid 11^n - 4^n$ with mathematical induction. This is what I wrote:

*

*For $n = 1$, we have $7 \mid 11^1 - 4^1 \Rightarrow 7 \mid 7$ which is obviously true. $\checkmark$


*Assume that the statement is true for $n = k$. So: $7 \mid 11^k - 4^k$ and therefore there is an integer such that $m$ such that: $11^k - 4^k = 7m$. Thus: $4^k = 11^k - 7m$.


*Now we prove its truth for $n = k + 1$. So we want to prove that $7 \mid 11^{k + 1} - 4^{k + 1}$. We can write this like this: $7 \mid \big(11\cdot11^k\big) - \big(4\cdot4^k\big)$ and since $4^k = 11^k - 7m$, so in fact we have to prove: $7 \mid \big(11 \cdot11^k\big) - \big(4\cdot(11^k - 7m)\big) \Longrightarrow 7 \mid 11\cdot11^k - 4\cdot11^k + 7(4m) \Longrightarrow 7 \mid 7\cdot11^k + 7(4m) \Longrightarrow 7 \mid 7(11^k + 4m)$.
But from here you can clearly see that $7(11^k + 4m)$ is divisible by 7. So according to the principle of mathematical induction, the statement is proved. $\blacksquare$
Now my question is, is this proof correct? And is there another way to prove this statement by mathematical induction?
 [/INST] Let's modify your induction proof so that we directly use the induction hypothesis that $7 \mid 11^k - 4^k$ for some positive integer $k$.
Let $P(n)$ be the the statement that $7 \mid 11^n - 4^n$.
You handled the $n = 1$ case correctly.
Since the statement $7 \mid 11^n - 4^n$ holds for $n = 1$, we may assume $P(k)$ holds for some positive integer $k$.  That is, $7 \mid 11^k - 4^k$ holds for some positive integer $k$.  Then there exists an integer $m$ such that $7m = 11^k - 4^k$.
Thus far, I have essentially reformulated what you said in your proof.  Now, we will express $11^{k + 1} - 4^{k + 1}$ in terms of $11^k - 4^k$ so that we can use the induction hypothesis in the induction step.
Let $n = k + 1$.  Then
\begin{align*}
11^{k + 1} - 4^{k + 1} & = 11 \cdot 11^k - 4 \cdot 4^{k}\\
                       & = (7 + 4)11^k - 4 \cdot 4^k\\
                       & = 7 \cdot 11^k + 4 \cdot 11^k - 4 \cdot 4^k\\
                       & = 7 \cdot 11^k + 4(11^k - 4^k)\\
                       & = 7 \cdot 11^k + 4 \cdot 7m && \text{by the induction hypothesis}\\
                       & = 7(11^k + 4m)
\end{align*}
Since $11^k + 4m$ is an integer, $7 \mid 11^{k + 1} - 4^{k + 1}$.  Thus, $P(k) \implies P(k + 1)$ for each positive integer $k$.  Since $P(1)$ holds and $P(k) \implies P(k + 1)$ for each positive integer $k$, $P(n)$ holds for each positive integer $n$ by the Principle of Mathematical Induction.
</s>