How to prove $47 \mid 49^{n} - 2^n $ by induction I|m not entirely sure if I'm allowed to ask this, please tell me if I'm not:
As homework our teacher told us to solve that $49^{n} - 2^n$ is divisible by $47$ with $n \in \mathbb N$ using induction. However I'm failing to do this.
If I would be allowed to use modulo calculation this would be proven in 2 lines but induction seems far more complicated to me.
 A: Using congruences : 
Base step :
$$47\mid 49^0 - 2^0 = 0$$
Inductive step :
Suppose for  a certain $n\in \Bbb N$ that :
$$47 \mid 49^{n} - 2^n$$
which can, equivalently, be expressed as
$$49^{n} \equiv 2^n [47]$$
Then $$49^{n+1} \equiv 2^n 49 \equiv 2^n 2 \equiv 2^{n+1}[47]$$
This ends the induction. Therefore, $$\forall n\in\Bbb N, 47\mid49^n-2^n.$$
A: $$49^{n+1}-2^{n+1}=49\cdot 49^n - 2\cdot 2^n = 49(49^n-2^n) +47\cdot2^n$$
And the right-hand side is divisible by $47$ if $49^n-2^n$ is.
A: Hint $\ {\rm mod}\ 47\!:\,\ 49\equiv 2\,\Rightarrow\, 49^n\equiv 2^n\,$ is special case of the Congruence Power Rule (below). You can either prove it as a Lemma, or mimic its inductive proof in this special case.
Congruence Power Rule $\rm\ \ \color{}{A\equiv a}\ \Rightarrow\ \color{#c00}{A^n\equiv a^n}\ \  (mod\ m)\ \ $ for all naturals $\rm\,n.$
Proof $\ $ For $\rm\,n=0\,$ it's $\,1\equiv 1\,$ so true. $\rm\,A\equiv a,\ A^n\equiv a^n \Rightarrow\, \color{#c00}{A^{n+1}\equiv a^{n+1}},\,$ by the Congruence Product Rule, so the result follows by induction on $\rm\,n.$
