How to prove $47 \mid 49^{n} - 2^n $ by induction

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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