Results 1 to 4 of 4
Like Tree3Thanks
  • 3 Post By romsek

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

  1. #1
    Member
    Joined
    Feb 2017
    From
    N/A
    Posts
    91

    Question 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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    5,595
    Thanks
    2359

    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
    Thanks from topsquark, phys251 and azollner95
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Dec 2016
    From
    Earth
    Posts
    103
    Thanks
    47

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

    You can also note:


    9^n + 56n + 63 =

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

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

    9^n + (64n + 64) - 1 - 8n


    64 divides (64n + 64), so it remains to show that 64 also divides  \ \ 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  \ \ n \ge 2:


    9^n - 1 - 8n =

    (8 + 1)^n - 1 - 8n =

    \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 =


    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  =


    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.
    Last edited by greg1313; Apr 4th 2017 at 02:37 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Dec 2013
    From
    Colombia
    Posts
    1,744
    Thanks
    571

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

    The induction step can be done as follows:

    \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 8 to divide (9^n + 7).

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

    QED
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: Oct 8th 2011, 04:16 PM
  2. Replies: 2
    Last Post: May 1st 2011, 02:11 PM
  3. In Z[i], show that 1+i divides...
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Apr 21st 2010, 02:37 PM
  4. Replies: 1
    Last Post: Feb 23rd 2010, 12:36 PM
  5. Replies: 7
    Last Post: Nov 7th 2009, 04:05 AM

/mathhelpforum @mathhelpforum