Results 1 to 8 of 8

Math Help - 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. 9^n-5^n is divisible by 4, for n\in\mathbb{N}_0


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


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


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


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


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

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    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. 9^n-5^n is divisible by 4, for n\in\mathbb{N}_0

    Attempt: Step 1: For n=1...
    9^1-5^1=4, which can be divided by 4.
    Therefore, n=1 is true...
     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...
    9^k\cdot9-5^k\cdot5+9\cdot5^k-5^k\cdot5 => 9[9^k-5^k]+9[9^k-4\mathbb{Z}]-5^k\cdot5 => 9\cdot4\mathbb{Z}+9\cdot9^k-36\mathbb{Z}-5\cdot5^k => 36\mathbb{Z}+9\cdot9^k-36\mathbb{Z}-5\cdot5^k => 9.9^k-5.5^k
    Last edited by GrigOrig99; July 7th 2012 at 08:39 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    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...
    9^k\cdot9-5^k\cdot5+9\cdot5^k-5^k\cdot5 => 9[9^k-5^k]+9[9^k-4\mathbb{Z}]-5^k\cdot5 => 9\cdot4\mathbb{Z}+9\cdot9^k-36\mathbb{Z}-5\cdot5^k => 36\mathbb{Z}+9\cdot9^k-36\mathbb{Z}-5\cdot5^k => 9.9^k-5.5^k
    It is easy. 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 (9^k-5^k)~\&~(9-5) are divisible by 4.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jul 2011
    Posts
    140

    Re: Divisibility Proofs

    So 9(9^k-5^k)+5^k(9-5) => 9(4\mathbb{Z})+5^k(4) => 36\mathbb{Z}+5^k\cdot4 => 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: 9 \equiv 1 (\mod 4) so 9^n \equiv 1 (\mod 4). Similarly, 5^n \equiv 1 (\mod 4).

    Therefore 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
    18,605
    Thanks
    1574
    Awards
    1

    Re: Divisibility Proofs

    Quote Originally Posted by GrigOrig99 View Post
    So 9(9^k-5^k)+5^k(9-5) => 9(4\mathbb{Z})+5^k(4) => 36\mathbb{Z}+5^k\cdot4 => 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.
    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: September 26th 2011, 03:51 AM
  2. Proof by Induction - Divisibility Proofs
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: September 20th 2011, 04:29 PM
  3. Proofs of rules of divisibility
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 24th 2010, 10:47 AM
  4. Proofs-Divisibility of Integers
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 14th 2009, 11:45 PM
  5. Replies: 3
    Last Post: October 6th 2007, 02:01 PM

Search Tags


/mathhelpforum @mathhelpforum