Prove $7$ divides $13^n- 6^n$ for any positive integer

Question

I need to prove $7|13^n-6^n$ for $n$ being any positive integer.

Using induction I have the following:

Base case:

$n=0$: $13^0-6^0 = 1-1 = 0, 7|0$

so, generally you could say:

$7|13^k-6^k , n = k \ge 1$

so, prove the $(k+1)$ situation:

$13^{(k+1)}-6^{(k+1)}$

$13 \cdot 13^k-6 \cdot 6^k$

And then I'm stuck....where do I go from here?

Answer 1

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

$13^{1}-6^{1}=7$

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

$13^{n}-6^{n}=7k$

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

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

$13\cdot13^{n}-6\cdot6^{n}=$

$(7+6)\cdot13^{n}-6\cdot6^{n}=$

$7\cdot13^{n}+6\cdot13^{n}-6\cdot6^{n}=$

$7\cdot13^{n}+6\cdot(\color{red}{13^{n}-6^{n}})=$

$7\cdot13^{n}+6\cdot\color{red}{7k}=$

$7\cdot13^{n}+7\cdot6k=$

$7\cdot(13^{n}+6k)$

---

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

Answer 2

Hint: $$13\equiv 6\bmod 7$$ rise both sides to the power of $n$.

Answer 3

Note

$$ 13\times 13^k -6 \times 6^k = 7\times 13^k +6(13^k-6^k) $$

Answer 4

Write $13=6+7$ to expand $13*13^k-6*6^k$.

Answer 5

Write $13^n-6^n=(14-1)^n-(7-1)^n$. Expand using the binomial theorem; the $1$'s cancel and you're left only with multiples of $7$.

Answer 6

There's always this:

$$\begin{split} x^2-y^2 &= (x-y)(x+y)\\ x^3-y^3 &= (x-y)(x^2+xy+y^2)\\ x^4-y^4 &= (x-y)(x^3 +x^2y+xy^2+y^3)\\ &\vdots\\ x^n-y^n &= (x-y)\left(\sum_{i=1}^{n}x^{n-i}y^{i-1}\right) \mid n\in \mathbb{N} \end{split}$$

In the above, let $x=13$ and $y=6$. Then you can visually see that no matter what $n\in \mathbb{N}$ is, $ 7\mid 13^n-6^n$. And more generally, $x-y \mid x^n-y^n$.