1. Not finding help here? Sign up for a free 30min 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!

Division Algorithm

  1. Jul 26, 2012 #1
    1. My difficulty is to show that if a is an integer such that 2 does not divide a and 3 does not divide a then 24 does not divide a squared minus 1

    2.Is there any equation which helps?

    3. My idea is that it has to be an integer such that 6 does not divide a..........therefore i have to show that 6a,6a+1,...6a+5 converted to asquared minus 1 are not divisible by 24........pls can anyone suggest if im solving it correctly.
     
  2. jcsd
  3. Jul 26, 2012 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Well, not "6a" because that would be divisible by both 2 and 3. And you don't mean "6a+ ...". If "2 does not divide a and 3 does not divide a" then either a= 6k+ 1 or a= 6k+ 5 for some integer k.

    Now, if a=6k+ 1, [itex]a^2- 1= 36k^2+ 12k+1-1= 36k^2- 12k= 12k(3k- 1)[/itex]. That will be divisible by 3 if either k or 3k-1 is even- and it is easy to see that they can't both be odd.

    If a= 6k+ 5, [itex]a^2-1= 36k^2+ 60k+ 25- 1= 36k^2+ 60k+ 24= 12(3k^2+ 5k+ 2)= 12(3k+ 2)(k+ 1)[/itex]. Now it is only necessary to show that 3k+2 and k+ 1 can't both be odd.
     
  4. Jul 26, 2012 #3
    how can i explain that 6k is divisible by 6 when if i change it to asquared - 1 (pls refer to previous message) it becomes 36ksquared - 1........thats not easy to explain as divisible by 6!:(
     
  5. Jul 26, 2012 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    The hypothesis is "a is an integer such that 2 does not divide a and 3 does not divide a" so [itex](6k)^2- 1[/itex] is not relevant.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Division Algorithm
  1. Divisibility Proofs (Replies: 2)

  2. Divisibility Proof (Replies: 10)

  3. Prove Divisibility (Replies: 7)

  4. Proof of divisibility (Replies: 3)

Loading...