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: Proving that 3^(6n)-2^(6n) is divisible by 8 using induction

  1. Jun 13, 2010 #1
    1. The problem statement, all variables and given/known data

    I am to prove that [tex]3^{6n}-2^{6n}[/tex] is divisible by 35 for all n[tex]n\in\aleph[/tex] using induction.

    2. Relevant equations

    [tex]3^{6n}-2^{6n}=35x[/tex] where [tex]x\in\aleph[/tex] for all [tex]n\in\aleph[/tex] and

    3. The attempt at a solution
    thus since 19 is an element of natural numbers the base case is true

    Then I make this assumption

    Inductive step:

    and i don't know where to go from here, i've tried lots of things, but i cant reduce it down to the assumption
  2. jcsd
  3. Jun 13, 2010 #2
    Do you know this fact: a (mod n) × b (mod n) = ab (mod n)?
  4. Jun 13, 2010 #3
    No i didn't know about that, and we haven't looked at modulus yet, so i'm not sure how to use it in this proof
  5. Jun 13, 2010 #4
    Ok. Then, suppose 36k = 35a+y. Then, 26k = 35b+y. (Why?) Substitute.
  6. Jun 13, 2010 #5
    im assuming it looks like this:


    [tex](3^{6} mod 35) (3^{6k} mod 35) - (2^{6} mod 35) (2^{6k} mod 35)=0[/tex]

    [tex]((29\cdot3^{6k}) mod 35) - ((29\cdot2^{6k}) mod 35)=0[/tex]

    [tex]29(3^{6k} mod 35 - 2^{6k} mod 35)=0[/tex]

    [tex](3^{6k} mod 35 - 2^{6k} mod 35)=0[/tex]
  7. Jun 13, 2010 #6
    That's right. You have to be careful when dividing both sides by the same thing in modular arithmetic, but it works out correctly this time. If you want to pursue this problem without explicitly using modular arithmetic, see my second post.
  8. Jun 13, 2010 #7
    Regarding post #4:

    i see that
    36k = 35a+y
    26k = 35b+y
    since any number can be expressed as a linear combination like you showed, but what allows us to assume that the remainder , y, are equivalent? Is it because we assume
    36k - 26k =35x that we must conclude from this that the remainders are the same in order for them to subtract to zero?
  9. Jun 13, 2010 #8
    Exactly so. Otherwise, there would be a contradiction.
  10. Jun 13, 2010 #9
    Thank you!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook