Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The problem asks to prove $8^{(n+2)}+9^{(2n+1)}$ is divisible by 73

Proof by induction:

We look at base case $n=1$ => which gives us $1241$ which is divisible by $73$; now for $n+k$

we know that $8^{(k+2)}+9^{(2k+1)}=73t$ for some integer $t$ then $$8^{(k+3)}+9^{(2k+3)}=8\cdot 8^{(k+2)}+81\cdot 9^{(2k+1)}$$

I am stuck on this step. I want to get $8^{(k+2)}+9^{(2k+1)}$ together so I can change them into $73t$ but don't know how to do it, or am I overthinking all of this.

share|cite|improve this question

You don't have to be clever, just comfortable with induction.

Suppose $73 | 8^{n+2}+9^{2n+1}$ ("$|$" means "divides exactly").

Putting $n+1$ for $n$, you want to show that this implies that $73 | 8^{n+3}+9^{2n+3}$ .

This will be true if $73$ divides their difference, which is $8^{n+3}+9^{2n+3}-(8^{n+2}+9^{2n+1})$.

Working this out, this is

$\begin{array} ( 8^{n+3}+9^{2n+3}-(8^{n+2}+9^{2n+1}) &=(8^{n+3}-8^{n+2}) +(9^{2n+3}-9^{2n+1})\\ &=8^{n+2}(8-1) +9^{2n+1}(9^2-1)\\ &=7 \cdot 8^{n+2} +80\cdot 9^{2n+1}\\ &=7 \cdot 8^{n+2} +(73+7)\cdot 9^{2n+1}\\ &=7 \cdot (8^{n+2}+9^{2n+1}) +73\cdot 9^{2n+1}\\ \end{array} $

By the induction assumption, $73 | 8^{n+2}+9^{2n+1}$, so $73$ divides this sum, and therefore divides $8^{n+3}+9^{2n+3}$.

I worked this out as I went along, and the only thing that might be considered "clever" is noticing that $80 = 73+7$. I guess that I "had" to do something at that point, because otherwise I would have been stuck. This also forced the induction hypothesis to come into play here. I find this interesting because it is used twice, once in computing the difference, and once in showing that the difference is divisible by 73.

It might be interesting to try to generalize this, because this kind of thing is rarely a coincidence.

share|cite|improve this answer

This can be done in various ways:

$$8\cdot 8^{k+2}+81\cdot 9^{2k+1}=8\cdot(8^{k+2}+9^{2k+1})+?$$ is one example.

Note also that any sequence of the form $a_n=r\cdot 8^n+s\cdot81^n$ satisfies a recurrence relation i.e. $$a_{n+2}-(8+81)a_{n+1}+8\cdot 81 a_n=0$$ where you can see how the coefficients are made up. Then you need two cases to get started, but it is obvious that divisibility persists.

share|cite|improve this answer
Note that both these forms essentially rely on the trick Cameron Williams notes. – Mark Bennet Mar 23 '14 at 21:50

Hint: Try adding and subtracting $8\cdot 9^{2k+1}$ (or $81\cdot 8^{k+2}$) and see what happens. The reason for doing this is that, as written, we can't immediately invoke the inductive hypothesis but if we introduce either of these terms, we would get exactly what we want.

share|cite|improve this answer
Would someone care to explain why my post has been marked for deletion? In Lay's book, this is exactly what he does for these kinds of problems. – Cameron Williams Mar 23 '14 at 21:46

Since we know by the induction hypothesis that: $$ 8^{k+2} + 9^{2k+1} = 73t $$ for some $t \in \mathbb Z$, try solving for one of the powers and substituting. For example, solving for the second power yields $9^{2k+1} = 73t - 8^{k+2}$ so that: \begin{align*} 8[8^{k+2}]+81[9^{2k+1}] &= 8[8^{k+2}]+81[73t - 8^{k+2}] \\ &= 8[8^{k+2}]+81[73t] - 81[8^{k+2}] \\ &= 81[73t] - 73[8^{k+2}] \\ &= 73\underbrace{[81t - 8^{k+2}]}_{\in ~\mathbb Z} \\ \end{align*}

share|cite|improve this answer

$\begin{eqnarray}{\bf Hint}\,\ \ {\rm mod}\ 73\!: &&\quad\, 8\ \equiv\ 9^2\\ {\rm times} \ &&8^{n+2}\equiv - 9^{2n+1}\\ \Rightarrow\ \ &&8^{n+3}\equiv -9^{2n+3}\ \ \text{is the induction step.} \end{eqnarray}$

share|cite|improve this answer
This method generalizes widely, see this answer. – Bill Dubuque Mar 24 '14 at 4:33

$\newcommand{\+}{^{\dagger}} \newcommand{\angles}[1]{\left\langle #1 \right\rangle} \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace} \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil #1 \right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\down}{\downarrow} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\isdiv}{\,\left.\right\vert\,} \newcommand{\ket}[1]{\left\vert #1\right\rangle} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left( #1 \right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert} \newcommand{\wt}[1]{\widetilde{#1}}$ \begin{align} \color{#00f}{\large 8^{n + 2} + 9^{2n + 1}}&=64 \times 8^{n} + 9\times 81^{n} =73 \times 8^{n} + 9\pars{81^{n} - 8^{n}} \\[3mm]&=73 \times 8^{n} + 9\pars{81 - 8}\sum_{j = 0}^{n - 1}81^{n - j - 1}8^{j} =\color{#00f}{\Large 73}\bracks{8^{n} + 9\sum_{j = 0}^{n - 1}81^{n - j - 1}8^{j}} \end{align}

share|cite|improve this answer

By the binomial theorem, $9^{2n}=81^n=(73+8)^n=73a+8^n$. Therefore,

$$8^{n+2}+9^{2n+1}=8^2\cdot 8^n +9\cdot 81^n=8^2\cdot 8^n +9(73a+8^n)=(8^2+9)\cdot 8^n+73(9a)=73(8^n+9a)$$

More generally, if $v=u+1$, then $v^2-u=u^2+v=u^2+u+1$ divides $u^{n+2}+v^{2n+1}$. Note that $u^2+v$ is the base case ($n=0$) for induction.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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