Results 1 to 6 of 6

Math Help - Prove divisibility

  1. #1
    Super Member
    Joined
    Oct 2007
    From
    London / Cambridge
    Posts
    591

    Prove divisibility

    I could use a little guidance for this questions.

    Let n be an integer greater than 6. Prove that if is n-1 and n+1 are both prime, then [tex]n^2(n^2+16) is divisible by 720. also is the converse true.
    My thoughts, given the conditions n must be an even number, so n=2k where k > 3

    also i know that [tex] n^2 - 1 = a*b[tex] where a and b are prime and b=a+2

    Could i have some help please, thanks in advance.
    Last edited by bobak; November 15th 2007 at 11:32 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Oct 2007
    From
    London / Cambridge
    Posts
    591
    anyone?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    As well as being an even number, n has to be a multiple of 3 (otherwise one of the numbers n1 and n+1 would have to be a multiple of 3. Therefore n is a multiple of 6 and so n^2 is a multiple of 36. Also, n^2+16 must be a multiple of 4.

    So far, that tells us that n^2(n^2+16) is a multiple of 364=144. To get it as a multiple of 720 we only need an extra factor of 5, so we want to show that either n or n^2+16 must be a multiple of 5. One way to do this is to work mod 10. A prime number greater than 5 has to end in 1, 3, 7 or 9. So an even number with a prime on both sides of it has to end in 0, 2 or 8. If n ends in 0 then it already has a factor of 5 in it. if n ends in a 2 or an 8 then n^2 ends in a 4, so n^2+16 ends in a 0 ...

    What about the converse? That had better not be true, otherwise there would be an easy way to construct an infinite number of prime pairs. So look for a counterexample (remembering that we started out by looking at n being a multiple of 6).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    I was going to respond yesterday but I completely forget.

    We want to show 720|(n^2(n^2+16)) since 720 = 5\cdot 3^2 \cdot 2^4 it is equivalent to saying 2^4|n^2(n^2+16), 3^2|n^2(n^2+16), 5|n^2(n^2+16).

    First we prove the case with 2^4. Since n\pm 1 are primes (greater than 6) it means n must be even because otherwise n\pm 1 shall not be primes. But then n^2 is divisible by 2^2 and n^2+4^2 is divisible by 2^2 so their product n^2(n^2+16) is divisible by 2^4.

    The next case is with 3^2. Now n=3k+j where 0\leq j\leq 2 by the division algorithm. It cannot be that n=3j+1 because otherwise n-1=3j cannot be prime (since it is greater than 6). Similarly n\not 3k+2 because then n+1=3(k+1) which is not prime. So n is divisible by 3. Thus, n^2 is divisible by 3^2.

    Finally the last case. By using the same argument as in the middle case we have n=5k\pm 2 meaning n\equiv \pm 2 (\bmod 5) thus n^2 \equiv 4 (\bmod 5)\implies n^2+16\equiv 0 (\bmod 5). Thus, n^2+16 is divisible by 5.

    EDIT: Opalg beat me by 1 minute .
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Oct 2007
    From
    London / Cambridge
    Posts
    591
    thank a lot to both of you for the help.
    I'm very new to modular arithmetic, I just read this article nrich.maths.org :: Mathematics Enrichment :: Modular Arithmetic to give me a start. (can you suggest better articles?)

    about the divisiblity of 5, I totally understand your mod10 argument Opalg, however ThePerfectHacker i don't understand how this works
     n=5k\pm 2 because if k is odd then that means that n would also be odd but the conditions give rise to n being an even number, sorry i am a bit new to this, could you explain in more detail how the mod 5 works?

    thank a lot for all your help,

    Bobak
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,212
    Thanks
    419
    Awards
    1
    Quote Originally Posted by bobak View Post
    I could use a little guidance for this questions.



    My thoughts, given the conditions n must be an even number, so n=2k where k > 3

    also i know that [tex] n^2 - 1 = a*b[tex] where a and b are prime and b=a+2

    Could i have some help please, thanks in advance.
    Consider n = 288. 288^2(288^2 + 16) is divisible by 720, but neither 287 nor 289 are prime. So the converse of the theorem is not true.

    -Dan
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove Divisibility
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: March 1st 2010, 04:17 PM
  2. Prove divisibility
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 29th 2009, 11:54 AM
  3. Prove divisibility by induction
    Posted in the Algebra Forum
    Replies: 9
    Last Post: June 2nd 2009, 01:14 PM
  4. Prove divisibility by 7 (using induction)
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 29th 2008, 12:12 PM
  5. Prove divisibility by induction
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: July 30th 2008, 01:58 PM

Search Tags


/mathhelpforum @mathhelpforum