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

Note

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

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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 6

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 7

We write $n=1$ and get $13 - 6 =7$( a multiple of $7$) Moving to the induction hypothesis, We assume that $n=k$, therefore $13^k - 6^k = 7b$($b$ shows that $7$ is a multiple of $13^k -6^k$ by $b$ times) Taking $k=1$ from above ($n=k=1$) then we get :

$13^1 - 6^1=13 - 6=7$.

Take one side of the equation and use the equivalent to its multiple in each in the form of $13-7$ or $7+6$ : $\pm$ the divisor($7$).

Either $13^k(7+6) - 6^k(6)$ or $13^k(13) - 6^k(13-7)$.

Taking $ 13^k(13) - 6^k(13 -7)$ gives $13^k(13) - 6^k(13) + 6^k(7)$.

Change the power $k$ on $6^k(13)$ to $13$ ;$13^k(6)$ $13^k(13) - 13^k(6) + 6^k(7)$

Factor out $13^k$ on the LHS $13^k(13-6) + 6^k(7)$ giving

$13^k(7) + 6^k(7)$. This can be compressed to:

$7(13^k + 6^k)$ Therefore now $b= 13^k + 6^k$ making it $7|(13^n - 6^n)$ valid for all positive integers values of $n$.