How do you prove that $5(7^n)+3(11^n)-8$ is divisible by $3$ for all natural numbers $n$?

Question

How do you prove that $5(7^n)+3(11^n)-8$ is divisible by $3$ for all natural numbers $n$? I have been trying to figure this out and kept reaching dead ends. I would be grateful for some help

Answer 1

If you are unfamiliar with modulo arithmetic:

• Since $7^n=(6+1)^n = 1^n + *\cdot 1^{n-1}6^1 + \cdots + *\cdot 1\cdot 6^{n-1} + * \cdot 6^n$, (where it's not important which numbers are in the positions marked by an asterisk), you can see that $7^n = 3k_1 + 1$ for some $k_1\in\mathbb N$
• Similarly, you can show that $11^k = (12-1)^n = 3k_2 + (-1)^n$ for some $k_2\in\mathbb N$, but in this case, that doesn't even matter, because $3\cdot 11^n$ is always divisible by $3$.

You also have $8 = 3\cdot 2 + 2$, so you have

$$\begin{align}5\cdot 7^n + 3\cdot 11^n - 8 &= 5\cdot (3k_1 + 1) + 3\cdot 11^n - 3\cdot 2 - 2 \\&= 3\cdot(5k_1 + 11^n - 2) + 5 - 2 \\&= 3\cdot(5k_1 + 11^n - 2) + 3 \\&= 3\cdot (5k_1 + 11^n - 2 + 1)\end{align}$$ which is clearly a multiple of $3$.

Answer 2

Using modular arithmetic: modulo $3$,

\begin{align*} 5\cdot 7^n + 3\cdot 11^n - 8 \equiv 2\cdot 1^n+0 -2 = 0 \end{align*}

for all $n$.