Prove by induction $(6^ − 1)(7^ − 1)$ is a multiple of $30$ for all natural number $n$

Question

I've tried multiple approaches that worked for me in other exercises. But here I always get stuck here:

$$(6^{k+1} -1)(7^{k+1} -1)= (6\cdot6^k -1)(7\cdot7^k -1)= 6(6^k -1) 7(7^k-1)+11.$$

Proving different approaches I always end up in something like this, and I don't know how to advance any further. Can anyone give me any tips in what I am missing?

Answer 1

$(6^n - 1)(7^n - 1) = ((5 + 1)^n - 1)((6 + 1)^n - 1)$

Answer 2

It's a little tricky, but you can prove it like this:

1. Prove by induction that $(6^n - 1) = 5k$

If $n=1$, it's automatic.

Suppose $(6^n - 1) = 5k$. Then $$(6^{n+1}-1) = 6(6^n-\frac{1}{6}) = 6(6^n-\frac{1}{6}+\frac{5}{6}-\frac{5}{6}) = 6(6^n-1+\frac{5}{6}) = 6(5k+\frac{5}{6}) = 5(6k+1)$$

2. Prove by induction that $(7^n-1) = 6k$

If $n=1$, it's automatic.

Suppose $(7^n - 1) = 6k$. Then $$(7^{n+1}-1) = 7(7^n-\frac{1}{7}) = 7(7^n-\frac{1}{7}+\frac{6}{7}-\frac{6}{7}) = 7(7^n-1+\frac{6}{7}) = 7(6k+\frac{6}{7}) = 6(7k+1)$$

3. Finally,

$$(6^n-1)\cdot(7^n-1) = 5k_1\cdot6k_2 = 30k_1k_2 \qquad \forall n \in \mathbb{N}$$

Answer 3

We assume $30 \vert (6^n - 1)(7^n - 1) $ and apply induction:

$$ 30 \vert (6^{n + 1} - 1)(7^{n + 1} - 1) $$ $$ 30 \vert (6^n - 1 + 5 \cdot 6^n)(7^n - 1 + 6 \cdot 7^n) $$ $$ 30 \vert (6^n - 1)(7^n - 1) + (6^n - 1)\cdot 6 \cdot 7^n + 5 \cdot 6^n(7^n - 1) + 30 \cdot 6^n \cdot 7^n $$

Now, it remains to show:

$$ 30 \vert (6^n - 1) 6 \cdot 7^n $$

or:

$$ 5 \vert 6^n - 1 $$

We do so inductively. We assume $5 \vert 6^n - 1$ and apply induction:

$$ 5 \vert 6^{n + 1} - 1 = 5 \vert 6^n - 1 + 5 \cdot 6^n $$

And so we conclude $30 \vert (6^n - 1)(7^n - 1)$ for all $n \geq 0$.