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!

Algebraic proofs of divisibility

  1. May 7, 2014 #1
    Hello,

    I have a problem with algebra and divisibility etc. I have a swedish textbook that really sucks. Not a good solutions section and no separate solutions manual either. Just a lot of proofs to show.

    At the moment I'm stuck at proofs with divisibility.

    I have two examples:

    1) Prove that if p is a prime number ≥ 3, then 24 | (p^2 - 1)

    2) Prove that if p is a prime number ≥ 3, then 3 | (2p^2 + 1)

    How to think and show this.

    I know that p can be written as 2k + 1 since all prime numbers larger than 3 are odd numbers.

    So in case 1) we have to show that 24 | 4k(k + 1) = 4(k^2 + k). But how?

    In case 2) we have to show that 3 | 8k^2 + 8k + 3 = 2(4k^2 + 4k) + 3 so we have to show that 3 is divisible by every other odd number? (This is due to the fact that 2(4k^2 + 4k) is an even number and if we add 3 we get the second odd number after... Again, how to show that the number is always divisible by 3...

    In general I'm having trouble with these type of questions...

    Hope some of you guys can help me develop my way of thinking...

    Thanks so very much in advance!
     
  2. jcsd
  3. May 7, 2014 #2

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    To get started on the first problem, note that ##p^2 - 1 = (p-1)(p+1)##. If ##p## is prime and ##\geq 3##, then ##p## is odd, so both ##p-1## and ##p+1## are even. Thus ##4 | (p^2 - 1)##. But you can actually conclude more than that. In fact ##8 | (p^2 - 1)## because either ##p-1## or ##p+1## must be divisible by ...?
     
  4. May 7, 2014 #3
    You'll want ##p>3##. Note that ##p=3## is a counterexample to both of those statements.
     
  5. May 7, 2014 #4

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Good catch, I didn't even notice that. :smile:
     
  6. May 8, 2014 #5
    Yeah, I agree that 4 | (p^2 - 1) since it is either divisible by (p + 1) or (p - 1) for all p. Also, 8 | (p^2 - 1) because both (p + 1) and (p - 1) are also divisible by 2. So, 8 = 2*4 | (p^2 - 1) = (p + 1)(p - 1). But the question that remains is how we can show that it is divisible by 24?

    24 can be written as 2*2*2*3 or 2*3*4. We have shown that (p^2 - 1) can divided by 2*2*2 = 2*4 but we also have to show that it can be dividied by 3... From the top of my head I get that if p = 7 or 11 we have 3 | p - 1 = 6 and 3 | p + 1 = 12 --> 24 | (p^2 - 1).

    But I want to understand how to prove that this is true for all p>3...
     
  7. May 8, 2014 #6
    Yeah sorry my bad. Wrote the question wrong. Although I cannot correct my original post...
     
  8. May 8, 2014 #7

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Consider the numbers p-1, p, and p+1. Exactly one of these must be divisible by 3. Can it be p?
     
  9. May 8, 2014 #8
    No, it cannot be p since if 3 | p > 3 then p would not be a prime number. And p-1, p, and p+1 three on each other following numbers --> 3 must be a divisor of at least one of them.

    This must mean that p^2 - 1 is divisible by 2, 3 and 4 --> it must be divisible by 24.

    So, this will be enough to prove that 24|p^2 - 1 given that p is a prime number > 3?
     
  10. May 8, 2014 #9

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    No, the implication does not follow. For example, 12 is divisible by 2, 3, and 4, but it is not divisible by 24.

    You need to use the fact that p^2 - 1 is divisible by 8 and 3. You just established divisibility by 3. In a previous post, you addressed divisibility by 8, but I'm not convinced by your proof:
    You need to argue as follows:
    * both p-1 and p+1 are divisible by 2
    * one of p-1 or p+1 must be divisible by 4
    * therefore, (p-1)(p+1) is divisible by 8
     
  11. May 8, 2014 #10
    Isn't that what I did?
    You need to argue as follows:
    * both p-1 and p+1 are divisible by 2 (because both p-1 and p+1 are even numbers)
    * one of p-1 or p+1 must be divisible by 4
    Yeah, I agree that 4 | (p^2 - 1) since either (p + 1) or (p - 1) is divisible by 4 for all p
    * therefore, (p-1)(p+1) is divisible by 8
    8 | (p^2 - 1) because both (p + 1) and (p - 1) are divisible by 2 and since also either p + 1 or p - 1 are divisible by 4 we have that 8 | (p^2 - 1) = (p+1)(p-1)
     
  12. May 8, 2014 #11
    Remember that p is a prime number > 3 so the smallest p > 3 is 7...
     
  13. May 8, 2014 #12

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    OK, sounds right.
    5, actually. :tongue: Anyway, I was taking issue with this:
    "is divisible by 2, 3, and 4" does not imply "must be divisible by 24", whereas "is divisible by 3 and 8" DOES imply "must be divisible by 24".
     
  14. May 8, 2014 #13
    Haha my bad...but still then p^2 - 1 = 24...

    But 8 = 2*4...so if it is divisible by 2 and 4 it is divisible by 8 and also divisible by 3 --> divisible by 24?

    But still. We have shown that it is divisible by 8 and 3 why does it become divisible by 24? Sorry if I'm slow and tired at the moment...
     
    Last edited: May 8, 2014
  15. May 8, 2014 #14

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    No, there are many numbers that are divisible by 2 and 4 but not by 8. Examples: 12, 20, 28, 44, ... So divisibility by 2 and 4 does not imply divisibility by 8. That's why you had to show it directly, by showing that one of the factors of ##p^2 - 1## is divisible by 2 and the other one is divisible by 4. Then the product is divisible by 8.
    Consider the prime factorization: divisibility by 8 means that there are at least three factors of 2, and divisibility by 3 means there is at least one factor of 3. Therefore the prime factorization looks like ##(2^n)(3^m)\cdots## where ##n \geq 3## and ##m \geq 1##. But ##24 = (2^3)(3^1)## so this shows that 24 is a divisor.
     
  16. May 8, 2014 #15
    His proof is fine. He stated that both p-1 AND p+1 are divisible by two and also either p-1 OR p+1is divisible b 4, so therefore 8|(p+1)(p-1).

    He just worded it badly at the end, but otherwise his proof is fine.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Algebraic proofs of divisibility
  1. Division Proof (Replies: 1)

Loading...