1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Prove this is divisible by 15

  1. Jan 11, 2013 #1
    1. The problem statement, all variables and given/known data
    Prove [itex] 4^{2n}-1 [/itex] is divisible by 15 for all positive integers
    3. The attempt at a solution
    Ok so I factor it into this
    [itex] (2^n+1)(2^n-1)(4^n+1) [/itex]
    I know how to get the factor of 3 because we know
    2^n is even so either 2^n+1 or 2^n-1 is divisible by 3 because we have 3 consecutive integers so at least one of them needs to be divisible by 3.
    But im not sure how to get the factor of 5.
    I thought about squaring some of their components and looking how close they
    are to 4^n+1.
  2. jcsd
  3. Jan 11, 2013 #2
    Consider the cases when n is odd and n is even. You should be able to obtain a factor of 5 from different terms in each case.
  4. Jan 11, 2013 #3


    User Avatar
    Homework Helper

    Did you not notice that [itex]4^2 = 16 = 15 + 1[/itex]?

    That suggests a proof, by induction on [itex]n[/itex], that [itex]4^{2n} = 15k_n + 1[/itex] for some integers [itex]k_1 = 1, k_2, k_3, \dots[/itex].
  5. Jan 11, 2013 #4
    You may also use the factorisation of:

    \left ( x^n - 1 \right ) = \left ( x - 1 \right ) \left ( x^{n-1} + \ldots + 1 \right )
  6. Jan 11, 2013 #5


    User Avatar
    Homework Helper

    Of course it would. Induction is a perfectly reasonable method of proof here.

    Assume [itex]4^{2k}-1=15N[/itex] for some integer N, and now prove that [itex]4^{2(k+1)}-1[/itex] is a multiple of 15.
  7. Jan 11, 2013 #6
    Well, I have found a solution :

    Let us assume that 42n-1 is divisible by 15.
    So, we have

    16n-1 is divisible by 16-1 ....

    Since 16n-1 = 16n - 1n .... it takes the form of an-bn is divisible by a-b. Just prove that it is possible and you have it ...
  8. Jan 11, 2013 #7


    User Avatar
    Homework Helper

    That's not exactly induction, but rather the method that jfgobin detailed, except that assuming 42n-1 is divisible by 15 does absolutely nothing for your proof.
  9. Jan 11, 2013 #8
    Yeah it requires proof by induction. Its pretty straight foward. You have a base case. Let n=1 and show it works. Then for the inductive case basically what you assume that
    15|4^(2k)-1 where k ε Z. Moreover we want to show that 15|4^(2k+2)-1. Then rewrite the notation as such were 15r=4^(2k)-1 where rεZ and 15n=4^(2k+2)-1 where nεZ. Also notice that 15n=4^(2k+2)-1 is just 15n=4^(2k)*16. From there its pretty much easy.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook