# Prove $10^{n+1}+3\cdot 10^n+5$ is divisible by $9$?

How do I prove that an integer of the form $10^{n+1}+3\cdot 10^{n}+5$ is divisible by $9$ for $n\geq 1$?I tried proving it by induction and could prove it for the Base case n=1. But got stuck while proving the general case. Any help on this ? Thanks.

• Hint. Check that $10^n\equiv 1\,(9)$. – Olivier Oloa Dec 27 '16 at 16:29
• By mathematical induction – Fawad Dec 27 '16 at 16:29

## 7 Answers

This can be proved by induction.

For $n=1$, the given expression becomes,

$10^{1+1}+3.10+5=135$ which is divisible by 9.

Let’s assume that the given statement is true for $k\ge1$, i.e., $10^{k+1}+3.10^k+5$ is divisible by $9$.

Then, $10^{(k+1)+1}+3.10^{k+1}+5=10^{k+2}+3.10^{k+1}+50-45$

=$10(10^{k+1}+3.10^k+5)-45$ is divisible by 9.

since $$10\equiv 1 \mod 9$$ we get $$10^{n+1}+3\cdot 10^n+5\equiv 1+3+5=9\equiv 0\mod 9$$

$10^{n+1}+3\cdot 10^{n}+5=10^{n}(10+3)+5=1300\cdots05$ has digit sum equal to $9$ and so is a multiple of $9$.

I would normally use congruences, but this can be done explicitly!

$$10^{n+1}+3\cdot 10^{n}+5 = 9 \cdot \underbrace{11 \cdots 1}_{n+1} + 1 + 9 \cdot \underbrace{33 \cdots 3}_{n} + 3 + 5 =\\= 9 \cdot (\underbrace{11 \cdots 1}_{n+1} + \underbrace{33 \cdots 3}_{n} + 1) = 9 \cdot 1\underbrace{44\cdots 4}_{n-1}5.$$

Proof by induction:

• Base case: $10^{0+1}+3\cdot10^{0}+5=18$
• Assumption: $10^{n+1}+3\cdot10^{n}+5=9k$
• Inductive step:

$10^{n+2}+3\cdot10^{n+1}+5=$

$10^{n+2}+3\cdot10^{n+1}+50-45=$

$10(\color\red{10^{n+1}+3\cdot10^{n}+5})-45=$

$10(\color\red{9k})-45=$

$9(10k)-45=$

$9(10k-5)$

Hint $\ {\rm mod}\ 9\!:\,\ \color{#c00}{10\equiv 1}\,\Rightarrow\,P(\color{#c00}{10})\equiv P(\color{#c00}1)\equiv$ sum of coefficients, for any polynomial $\,P(x)\,$ with integer coefficients, by the Polynomial Congruence Rule. See also Casting Out Nines.

Let $S(n)$ be the statement: $10^{n+1}+3\cdot{10^{n}}+5$ is divisible by $9$

Basis step: $S(1)$:

$\Rightarrow 10^{(1)+1}+3\cdot{10^{(1)}}+5=10^{2}+30+5$

$\hspace{45.5 mm}=100+35$

$\hspace{45.5 mm}=135$, which is divisible by $9$

Inductive step:

Assume $S(k)$ is true, i.e. assume that $10^{k+1}+3\cdot{10^{k}}+5$ is divisible by $9$

$\hspace{59 mm} \Rightarrow 10^{n+1}+3\cdot{10^{n}}+5=9A$

$\hspace{59 mm} \Rightarrow 10\cdot{10^{n}}+3\cdot{10^{n}}+5=9A$

$\hspace{59 mm} \Rightarrow 13\cdot{10^{n}}+5=9A$

$\hspace{59 mm} \Rightarrow 10^{n}=\dfrac{9A-5}{13}$

Then, $S(k+1)$: $10^{(k+1)+1}+3\cdot{10^{(k+1)}}+5$

$\hspace{23.5 mm} =10^{k+2}+3\cdot{10}\cdot{10^{k}}+5$

$\hspace{23.5 mm} =100\cdot{10^{k}}+30\cdot{10^{k}}+5$

$\hspace{23.5 mm} =130\cdot{10^{k}}+5$

$\hspace{23.5 mm} =130\cdot{\bigg(\dfrac{9A-5}{13}\bigg)}+5$

$\hspace{23.5 mm} =10\cdot{(9A-5)}+5$

$\hspace{23.5 mm} =90A-50+5$

$\hspace{23.5 mm} =90A-45$

$\hspace{23.5 mm} =9\hspace{1 mm}(10A-5)$, which is divisible by $9$

So, $S(k+1)$ is true whenever $S(k)$ is true.

Therefore, $10^{n+1}+3\cdot{10^{n}}+5$ is divisible by $9$.