# Thread: Show that 64 divides 9^n + 56n + 63

1. ## Show that 64 divides 9^n + 56n + 63

Show that 64 divides 9^n + 56n + 63 for all positive integers n.

Based off of basic computation I can see that for numbers like n=1, n=2, etc this holds but how would I show it for all positive integers?

2. ## Re: Show that 64 divides 9^n + 56n + 63

are you familiar with induction?

$9 + 56 + 63 = 128 = 2 \cdot 64$

so this is true for $n=1$ and we would say $P_1 = True$

next, we assume that $P_n=True$ and we use this to show that $P_{n+1} = True$

here we'd do

\begin{align*} &9^{n+1} + 56(n+1) + 63 \\ = &~9^n\cdot 9 + 56n + 56 + 63 \\ = &~9^n+ 56n + 63 + 8\cdot 9^n + 56 \\ = &~64k + 8\cdot 9^n + 56 \text{; because }P_n=True \\ =&~64k + 8(7+9^n) \end{align*}

clearly $64k$ is divisible by $64$ so we need to show that $8(7+9^n)$ is divisible by $64$ or alternatively that

$(7+9^n)$ is divisible by $8$

Using the same method we are using to show the original statement

$n=1 \Rightarrow 7+9^n = 16 = 2\cdot 8$ so $\tilde{P}_1=True$

Now you show that $\tilde{P}_n \Rightarrow \tilde{P}_{n+1}$ for this and thus that $7+ 9^n$ is divisible by 8

and you will have shown that

$9^{n+1} + 56(n+1) + 63$ is divisible by $64$

and thus that for the original statement

$P_n \Rightarrow P_{n+1}$

and thus it is True for all $n\geq 1$

so see if you can prove that $\tilde{P}_n \Rightarrow \tilde{P}_{n+1}$ it's not hard

3. ## Re: Show that 64 divides 9^n + 56n + 63

You can also note:

$\displaystyle 9^n + 56n + 63 =$

$\displaystyle 9^n + 56n + (8n - 8n) + 63 + (1 - 1) =$

$\displaystyle 9^n + (56n + 8n) + (63 + 1) - 1 - 8n =$

$\displaystyle 9^n + (64n + 64) - 1 - 8n$

64 divides (64n + 64), so it remains to show that 64 also divides $\displaystyle \ \ 9^n - 1 - 8n$.

It has been shown or mentioned it's true for n = 1 in at least one prior post. Let's look at $\displaystyle \ \ n \ge 2$:

$\displaystyle 9^n - 1 - 8n =$

$\displaystyle (8 + 1)^n - 1 - 8n =$

$\displaystyle \bigg(8^n \ + \ n\cdot8^{n - 1} \ + \ \dfrac{n(n - 1)}{2}8^{n - 2} \ + \ . . . \ + \ \dfrac{n(n - 1)}{2}8^2 \ + \ n\cdot8^1 \ + \ 1\bigg) \ - \ 1 \ - \ 8n =$

$\displaystyle 8^n \ + \ n\cdot8^{n - 1} \ + \ \dfrac{n(n - 1)}{2}8^{n - 2} \ + \ . . . \ + \ \dfrac{n(n - 1)}{2}8^2 \ + \ 8n \ - \ 8n \ + \ 1 \ - \ 1 =$

$\displaystyle 8^n \ + \ n\cdot8^{n - 1} \ + \ \dfrac{n(n - 1)}{2}8^{n - 2} \ + \ . . . \ + \ \dfrac{n(n - 1)}{2}8^2$ . . . . . . . . . **

The fractions in front of the powers of eights are combinations and are thus positive integers. The smallest power of eight is equal to 64,
so this expression is also divisible by 64.

** . . . . If n = 2, there will only be one term here. If n = 3, there will only be two terms here. And so on.

4. ## Re: Show that 64 divides 9^n + 56n + 63

The induction step can be done as follows:

\displaystyle \begin{align*}9^{n+1} + 56(n+1) + 63 &= 9\cdot 9^n + 56n + 56 + 63 \\ &= 8( 9^n + 7) + (9^n + 56n + 63) \end{align*}

where the final parenthesis is a multiple of 64 by the inductive hypothesis. So all we need is for $\displaystyle 8$ to divide $\displaystyle (9^n + 7)$.

$\displaystyle 9^n + 7 \equiv 1^n - 1 \pmod{8} = 1-1 \pmod{8} = 0 \pmod{8}$

QED