Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 dont know how to do it, or am i over thinking all of this.

share|improve this question

6 Answers 6

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|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|improve this answer
    
Note that both these forms essentially rely on the trick Cameron Williams notes. –  Mark Bennet Mar 23 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|improve this answer
3  
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 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|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|improve this answer
    
This method generalizes widely, see this answer. –  Bill Dubuque Mar 24 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|improve this answer

Your Answer

 
discard

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.