Mathematical Induction Divisibility Problem

Question

Prove that if $n \ge 1$ is a positive integer, then $13^n − 6^n$ is divisible by $7$.

In proving the $n = k+1$ case, I get to $133k + 6^k\cdot13 - 6\cdot13^k = 7M$, where $M$ is a positive integer. $133k$ is divisible by $7$. How do I show the $6^k\cdot13 - 6\cdot13^k$ part is divisible by $7$?

Answer 1

$13^{k+1} - 6^{k+1} = 13^k* 13 - 6^k * 6 = 13^k(7 + 6) - 6^k*6 = 7*13^k + 6*13^k - 6^k*6 = 7*13^k + 6(13^k - 6^k) = 7*13^k + 6(7*M) = 7*(13^k + k)$ is a multiple of 7.

Answer 2

$6^k\cdot13 - 6\cdot13^k = 6\cdot 13(6^{k-1}-13^{k-1}) = 6\cdot 13\cdot 7N$ by inductive hypothesis

Answer 3

Another approach:

By using the identity $$a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+\ldots+b^{n-1})\qquad n\in\mathbb{Z},n>0$$ you get $$13^n-6^n=7(13^{n-1}+13^{n-2}\cdot 6+\ldots+6^{n-1})$$ for every integer $n>0$.

Answer 4

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\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 5

The Induction Step: 13^(k+1) - 6^(k+1) = (13^k)(7+6) - (6^k)*6 = (13^k)7 + 6(13^k - 6^k) = (13^k)*7 + 6*7*m, since 7|(13^k - 6^k) (By the Induction Hypothesis). Therefore, 13^(k+1) - 6^(k+1)= 7*((13^k) + 6*m), so 7| 13^(k+1) - 6^(k+1). Hence, by the Principle of Mathematical Induction, it holds for all natural n.