How to prove that $7^n+3n+8$ is divisible by $9$ for $n\ge1$?

Question

I can prove $7^n+3n+8$ (see below) is divisible by $3$ for $n\ge1$ but cannot prove it is divisible by $9$.

My attempts gave me only following: $$7^n+3n+8=(7^n-1)+1+3n+8=(7^n-1)+3n+9=(7-1)(7^{n-1}+7^{n-2}+...+7+1)+3(n+3)=6(7^{n-1}+7^{n-2}+...+7^2+7+1)+3(n+3)=3[2(7^{n-1}+7^{n-2}+...+7^2+7+1)+n+3]=3[14(7^{n-2}+7^{n-3}+...+7)+n+19]$$ Thus, it is divisible by $3$ regardless of the parity of $n$. If $n$ is odd, it's divisible by $6$, yet, I can't see how it's divisible by $9$. I appreciate the help given by all of you.

Answer 1

Proof by Induction.

For $n=1$, $7+3+8= 18$ is divisible by $9$.

Inductive Hypothesis: Assume that the result is true for any $n=m$.

Thus, $7^m + 3m + 8 = 9\lambda$ where, $\lambda \in \mathbb{Z}$

$\implies 7^{m+1}= 7(9\lambda - 3m -8)$

Now, for $n=m+1$

$7^{m+1}+ 3(m+1)+8 = 7(9\lambda - 3m -8)+3m+11= 63\lambda -18 m - 45 = 9(7\lambda - 2m - 5)$ which is clearly divisible by $9$.

Hence, the result is true $\forall \space{} n \in \mathbb{N}$

Answer 2

Let $x_n = 7^n+3n+8$. It is natural to look for a recurrence of the form $x_{n+1} = 7x_n +an +b$.

Plugging $n=0$ and $n=1$ gives $x_{n+1} = 7x_n -18n -45$.

Thus, $x_{n+1}$ is a multiple of $9$ iff $x_{n}$ is a multiple of $9$.

Since $x_0=9$, the result follows by induction.

Answer 3

Hint

$7^3=1 \mod 9$

For $n=(1,2,3) \,\quad7^n={7,4,1} \mod 9$

Answer 4

Use congruence classes mod $9$. First note that $7$ has order $3\bmod 9$: $$7\equiv -2,\quad 7^2\equiv (-1)^2\equiv 4,\quad 7^3\equiv (-2)^2(-2)\equiv -8\equiv 1\mod 6.$$ So we'll classify $n$ by its congruence class $\bmod 3$.

• if $n\equiv 0\mod 3$, $7^n+8\equiv 1-1= 0\mod 9$, and $\;n\equiv 0\mod 3\implies 3n\equiv 0\mod 9\mkern1mu$;
• if $n\equiv 1\mod 3$, $7^n+8\equiv -1-1= -3\mod 9$, and $3n\equiv 3\mod 9\mkern1mu$;
• if $n\equiv 2\mod 3$, $7^n+8\equiv 4-1= 3\mod 9$, and $3n\equiv 6\equiv -3\mod 9$.

In all cases, the expression is congruent to $0$ mod $9.

Answer 5

$7^n +3n + 8 = (2*3 + 1)^n + 3n + 8=$

$(2*3 + 1)^n = \sum\limits_{k=0}^n {n\choose k}2^k3^k$. If $k\ge 2$ then $9|3^k$ so $\sum\limits_{k=0}^n {n\choose k}2^k3^k \equiv \sum\limits_{k=0}^1 {n\choose k}2^k3^k \equiv 1 + n*2*3 \equiv 6n + 1\mod 9$.

So $7^n +3n + 8 = (2*3 + 1)^n + 3n + 8\equiv 6n + 1 + 3n + 8\equiv 9n + 9 \equiv 0 \mod 9 $

...

A cuter way is note that:

$7^1 \equiv -2 \mod 9$

and $7^2 \equiv (-2)^2 \equiv 4 \mod 9$.

And $7^3 \equiv -8 \equiv 1 \mod 9$.

So for $n\equiv k \mod 3$

$7^n + 3n + 8\equiv 7^k + 3k + 8\mod 9$.

If $k = 0$ we have $1 + 8\equiv 9 \mod 9$. If $k = 1$ we have $-2 +3 + 8 \equiv 9 \mod 9$. If $k = -1$ we have $4 -3 + 8\equiv 9\mod 9$.

Answer 6

Hint:   using the identity $\,a^n-1 = (a-1)(a^{n-1}+a^{n-2}+\ldots+1)\,$ a few times:

$$ \begin{align} 7^n\color{red}{-1}\color{blue}{-6n}+3n\color{blue}{+6n}+8\color{red}{+1} &= 7^n-1-6n+9n+9 \\ &= (7-1)(7^{n-1}+ 7^{n-2}+\ldots+1)-6n+9(n+1) \\ &= 6 \Big((7^{n-1}-1)+(7^{n-2}-1)+\ldots+(1-1)\Big)+ 9(n+1) \\ &= 6 \cdot 6 \cdot (\;\ldots\;)+9(n+1) \end{align} $$