Prove that $13^n -4^n$ is divisible by $9$ for every integer $\geq $

Question

Prove that $13^n - 4^n$ is divisible by $9$ for every integer $n$ is greater than or equal to $1$.

I have written down my answer but I don't know if it is correct.

$ 13(13^k) - 4^{(k+1)}$
$= 9(13^k) + 4(13^k) - 4{(4^k)}$
$= 9(13^k) + 4(13^k - 4^k)$
$= 9(13^k) + 4(9a)$ where $9a = 13^k -4^k$
$= 9(13^k + 4a)$
$= 9b$ where $b=13^k + 4a$

Answer 1

Just use $a^n -b^n=(a-b)(a^{n-1} + ... + b^{n-1})$

Another way is using induction by n as you did it (more or less) in the OP.

Answer 2

Take base case $ n=1$, $9$ is divisible by $9$. Assume it to be true for $ n>=1$, then replace $n$ by $n+1$.

$13.13^n -4.4^n $ can be written as $9.13^n \, + 4.(13^n-4^n)$ and both parts of it are divisible by 9.

Answer 3

You can prove this by induction.

---

First, show that this is true for $n=1$:

$13^{1}-4^{1}=9$

Second, assume that this is true for $n$:

$13^{n}-4^{n}=9k$

Third, prove that this is true for $n+1$:

$13^{n+1}-4^{n+1}=$

$13\cdot13^{n}-4\cdot4^{n}=$

$13\cdot13^{n}-(13-9)\cdot4^{n}=$

$13\cdot13^{n}-13\cdot4^{n}+9\cdot4^{n}=$

$13\cdot(\color\red{13^{n}-4^{n}})+9\cdot4^{n}=$

$13\cdot\color\red{9k}+9\cdot4^{n}=$

$9\cdot13k+9\cdot4^{n}=$

$9\cdot(13k+4^{n})$

---

Please note that the assumption is used only in the part marked red.

Answer 4

since $$13\equiv 4 \mod 9$$ we get $$13^n-4^n\equiv 4^n-4^n\equiv 0 \mod 9$$