Results 1 to 8 of 8

Thread: Divisibility Proofs

  1. #1
    Member
    Joined
    Jul 2011
    Posts
    140

    Divisibility Proofs

    Having a bit of trouble with this one. At the point marked A, I'm not sure I'm going in the right direction. Immediately after that line I have B, which I'm showing as a possible alternative, but I'm unsure of that approach as well. Can anyone help me work out which, if either, of the two methods is correct?


    Many thanks.


    Q. $\displaystyle 9^n-5^n$ is divisible by 4, for $\displaystyle n\in\mathbb{N}_0$


    Attempt: Step 1: For $\displaystyle n=1$...
    $\displaystyle 9^1-5^1=4$, which can be divided by $\displaystyle 4$.
    Therefore, $\displaystyle n=1$ is true...


    Step 2: For $\displaystyle n=k$...
    Assume $\displaystyle 9^k-5^k=4\mathbb{Z}$, where $\displaystyle \mathbb{Z}$ is an integer...1
    Show that $\displaystyle n=k+1$ is true...
    i.e. $\displaystyle 9^{k+1}-5^{k+1}$ can be divided by $\displaystyle 4$
    $\displaystyle 9^{k+1}-5^{k+1}$ => $\displaystyle 9^1\cdot9^k-5^1\cdot5^k$ =>


    A $\displaystyle (9-5)[9^k-5^k]$ => $\displaystyle 4[4\mathbb{Z}]$...from 1 above => $\displaystyle 4[4\mathbb{Z}]$, which can be divided by 4


    B $\displaystyle 9[4\mathbb{Z}-5^k]-5[9^k-4\mathbb{Z}]$


    Thus, assuming $\displaystyle n=k$, we can say $\displaystyle n=k+1$ is true & true for $\displaystyle n=2,3,$... & all $\displaystyle n\in\mathbb{N}_0$
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,147
    Thanks
    3035
    Awards
    1

    Re: Divisibility Proofs

    Quote Originally Posted by GrigOrig99 View Post
    Having a bit of trouble with this one. At the point marked A, I'm not sure I'm going in the right direction. Immediately after that line I have B, which I'm showing as a possible alternative, but I'm unsure of that approach as well. Can anyone help me work out which, if either, of the two methods is correct?
    Q. $\displaystyle 9^n-5^n$ is divisible by 4, for $\displaystyle n\in\mathbb{N}_0$

    Attempt: Step 1: For $\displaystyle n=1$...
    $\displaystyle 9^1-5^1=4$, which can be divided by $\displaystyle 4$.
    Therefore, $\displaystyle n=1$ is true...
    $\displaystyle 9^{k+1}-5^{k+1}= 9^{k+1}-9\cdot 5^{k}+ 9\cdot 5^{k}-5^{k+1}.$
    Now factor.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jul 2011
    Posts
    140

    Re: Divisibility Proofs

    Ok, this is what I end up with but I've basically gone around in a circle...
    $\displaystyle 9^k\cdot9-5^k\cdot5+9\cdot5^k-5^k\cdot5$ => $\displaystyle 9[9^k-5^k]+9[9^k-4\mathbb{Z}]-5^k\cdot5$ => $\displaystyle 9\cdot4\mathbb{Z}+9\cdot9^k-36\mathbb{Z}-5\cdot5^k$ => $\displaystyle 36\mathbb{Z}+9\cdot9^k-36\mathbb{Z}-5\cdot5^k$ => $\displaystyle 9.9^k-5.5^k$
    Last edited by GrigOrig99; Jul 7th 2012 at 09:39 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,147
    Thanks
    3035
    Awards
    1

    Re: Divisibility Proofs

    Quote Originally Posted by GrigOrig99 View Post
    Ok, this is what I end up with but I've basically gone around in a circle...
    $\displaystyle 9^k\cdot9-5^k\cdot5+9\cdot5^k-5^k\cdot5$ => $\displaystyle 9[9^k-5^k]+9[9^k-4\mathbb{Z}]-5^k\cdot5$ => $\displaystyle 9\cdot4\mathbb{Z}+9\cdot9^k-36\mathbb{Z}-5\cdot5^k$ => $\displaystyle 36\mathbb{Z}+9\cdot9^k-36\mathbb{Z}-5\cdot5^k$ => $\displaystyle 9.9^k-5.5^k$
    It is easy. $\displaystyle 9^{k+1}-9\cdot 5^{k}+ 9\cdot 5^{k}-5^{k+1}=9(9^k-5^k)+5^k(9-5)$

    You know that both $\displaystyle (9^k-5^k)~\&~(9-5)$ are divisible by $\displaystyle 4$.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jul 2011
    Posts
    140

    Re: Divisibility Proofs

    So $\displaystyle 9(9^k-5^k)+5^k(9-5)$ => $\displaystyle 9(4\mathbb{Z})+5^k(4)$ => $\displaystyle 36\mathbb{Z}+5^k\cdot4$ => $\displaystyle 4(9\mathbb{Z}+5^k)$

    That leaves me with the 5^k though...Is that permitted, or am I still missing something?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Jun 2012
    From
    AZ
    Posts
    616
    Thanks
    97

    Re: Divisibility Proofs

    An alternate solution: $\displaystyle 9 \equiv 1 (\mod 4)$ so $\displaystyle 9^n \equiv 1 (\mod 4)$. Similarly, $\displaystyle 5^n \equiv 1 (\mod 4)$.

    Therefore $\displaystyle 9^n - 5^n \equiv 1 - 1 \equiv 0 (\mod 4)$ so it must be a multiple of 4.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,147
    Thanks
    3035
    Awards
    1

    Re: Divisibility Proofs

    Quote Originally Posted by GrigOrig99 View Post
    So $\displaystyle 9(9^k-5^k)+5^k(9-5)$ => $\displaystyle 9(4\mathbb{Z})+5^k(4)$ => $\displaystyle 36\mathbb{Z}+5^k\cdot4$ => $\displaystyle 4(9\mathbb{Z}+5^k)$

    That leaves me with the 5^k though...Is that permitted, or am I still missing something?
    The sum of two multiples of four is a multiple of four.
    $\displaystyle 9(9^k-5^k)+5^k(9-5)$ is the sum of two multiples of four.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Jul 2011
    Posts
    140

    Re: Divisibility Proofs

    Ok. Thank you.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by Induction - Divisibility Proofs
    Posted in the Pre-Calculus Forum
    Replies: 5
    Last Post: Sep 26th 2011, 04:51 AM
  2. Proof by Induction - Divisibility Proofs
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: Sep 20th 2011, 05:29 PM
  3. Proofs of rules of divisibility
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Jan 24th 2010, 11:47 AM
  4. Proofs-Divisibility of Integers
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 15th 2009, 12:45 AM
  5. Replies: 3
    Last Post: Oct 6th 2007, 03:01 PM

Search Tags


/mathhelpforum @mathhelpforum