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.

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

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:








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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.