Results 1 to 11 of 11

Math Help - Divisibility of [(p^2) - 1] by 6,12,24 etc. where p is prime number greater than 5

  1. #1
    Junior Member
    Joined
    Jun 2010
    Posts
    39

    Divisibility of [(p^2) - 1] by 6,12,24 etc. where p is prime number greater than 5

    p is a prime number greater than 5

    Discuss the divisibility of [(p^2) - 1] by 6,12,24....
    Is [(p^2) - 1] always divisible by 6, 12, 24. Yes? No? Why?
    What's the logic?

    Is this some kind of a series?
    Is there a proof?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    I would suggest a proof by induction when k\geq 7 where k is prime for each case.

    P(7):6x=49-1\rightarrow 6x=48 so P(7) is true

    Assume P(k):6x=k^2-1 is true

    P(k+1):6x=(k+1)^2-1\rightarrow 6x=k^2+2k+1-1\rightarrow 6x=(k^2-1)+2k+1

    The question is does 6|(2k+1) now
    Last edited by dwsmith; June 27th 2010 at 10:09 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jun 2010
    Posts
    39
    Not sure, but isn't induction used when you are proving something for n = natural number. Here we have 'p' prime. So induction doesn't seem to be the appropriate method.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Quote Originally Posted by swordfish774 View Post
    p is a prime number greater than 5

    Discuss the divisibility of [(p^2) - 1] by 6,12,24....
    Is [(p^2) - 1] always divisible by 6, 12, 24. Yes? No? Why?
    What's the logic?

    Is this some kind of a series?
    Is there a proof?
    First allow me to generalize and modify your question.
    Instead of a prime number  p , I'll consider an integer  a that is relatively prime to 6, and the result will imply the case for p\geq5. Also, it's enought to show divisibility by 24 and then it implies divisibility by any divisor of 24, in particular 6, 12, 24.
    Begin with a=\pm 1+6k (agree?) for some integer  k , then square both sides: a^2=1\pm 12k+36k^2=1\pm 12k\cdot(1\pm 3k) (The signs are respectively). Finally, a^2-1=\pm 12k\cdot(1\pm 3k) and either  k or 1+3k is even, and you have divisibility by 24.
    To answer your question: Yes and notice it's not special to primes geater than or equal to 5, but to all integers that are relatively prime to 6.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Quote Originally Posted by dwsmith View Post
    I would suggest a proof by induction when k\geq 7 where k is prime for each case.

    P(7):6x=49-1\rightarrow 6x=48 so P(7) is true

    Assume P(k):6x=k^2-1 is true

    P(k+1):6x=(k+1)^2-1\rightarrow 6x=k^2+2k+1-1\rightarrow 6x=(k^2-1)+2k+1

    The question is does 6|(2k+1) now
    I don't think so ( 2k+1 is odd, whereas 6 is even). Note that you wrote 6x=k^2-1 (tacit assumption that  k must be odd). You also wrote that 6x=(k+1)^2-1, but then k+1 is even and (k+1)^2-1 is odd. So P(k+1) is impossible.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jun 2008
    Posts
    148
    To rearrange the question, you want to know when p^2 - 1 | 3 \cdot 2^n for n = 1,2,3...

    We know that for any such prime, we have p \equiv 1,-1 mod(4) and p \equiv 1,-1 mod(3).

    As p^2 - 1 = (p-1) \cdot (p+1) it follows from the above that p^2 - 1 is always divisible by 3 \cdot 2^2.

    The really interesting question to ask is when is p^2 - 1 | 2^n for n > 2.

    It can be shown that if the equation  x^{2^{n-1}} + 1 \equiv 0 mod(p) has a solution x then 2^n |p^2 - 1, as 2^n | p-1.

    Can you figure out why?

    This however doesn't identity all of the primes for which 2^n |p^2 - 1. The question on when does p+1 | 2^n is pretty tough.
    Last edited by jamix; June 27th 2010 at 11:36 AM. Reason: typo
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by jamix View Post
    To rearrange the question, you want to know when p^2 - 1 | 3 \cdot 2^n for n = 1,2,3...

    We know that for any such prime, we have p \equiv 1,-1 mod(4) and p \equiv 1,-1 mod(3).

    As p^2 - 1 = (p-1) \cdot (p+1) it follows from the above that p^2 - 1 is always divisible by 3 \cdot 2^2.

    The really interesting question to ask is when is p^2 - 1 | 2^n for n > 2.

    It can be shown that if the equation  x^{2^{n-1}} + 1 \equiv 0 mod(p) has a solution x then 2^n |p^2 - 1, as 2^n | p-1.

    Can you figure out why?

    This however doesn't identity all of the primes for which 2^n |p^2 - 1. The question on when does p+1 | 2^n is pretty tough.
     p\equiv1\bmod{4}\implies p-1\equiv0\bmod{4} and  p+1\equiv2\bmod{4} . Thus  p^2-1\equiv0\bmod{8} .

    The same applies for when  p\equiv -1\bmod{4} .

    So we then have  3\cdot8\mid p^2-1 as it was already shown  3\mid p^2-1 .
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Jun 2008
    Posts
    148
    Yeah, I think I missed melese's post where he/she mentioned this.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Isn't it impossible for  p>3 to have ( p^2-1)|2^n?
    p^2-1=(p-1)\cdot(p+1) and when you have two consecutive even integers one of them is not divisible by 4, namely, has an odd divisor greater than 1.
    Another thing. If (p+1)|2^n, then p+1 must be a power of two itself. So a necessary (and sufficient) condition is to have p+1=2^k for some integer k\leq n, then it follows that  p is a Mersenne prime. Do you agree?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Jun 2010
    Posts
    39
    @ melese

    Brilliant! I understood. The best part was the 'prime relative to 6' part.

    @jamix

    I don't understand the symbols '|' 'mod' and the 3-lined symbol. Can you please elaborate.


    other queries: How do you insert the equations as images?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Jun 2008
    Posts
    148
    I meant to write 2^n | p^2 - 1 and 2^n | p+1.

    swordfish....

    For writing math symbols, use the TEX button (see LATEX section of this forum for more details).

    "mod(p)" means the remainder when an integer is divided by p. For example 7 \equiv 2 mod(5) because 2 is the remainder upon dividing 7 by 5. You could think of it as \frac{7}{5} = 1 + \frac{2}{5}.

    The sign "|" is a division sign. For example when I say what is 3 | 12, I'm asking for "12 divided by 3".

    Does this make sense?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prime Divisibility Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 25th 2011, 09:04 AM
  2. Divisibility by prime
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: April 16th 2010, 09:57 AM
  3. Prime Numbers and Divisibility
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 11th 2009, 12:21 PM
  4. Prime Numbers and Divisibility
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 10th 2009, 12:36 PM
  5. Some Prime Number Divisibility Questions
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 19th 2009, 08:17 PM

Search Tags


/mathhelpforum @mathhelpforum