Results 1 to 6 of 6

Thread: 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; Nov 15th 2007 at 10: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
    10
    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 $\displaystyle n^2$ is a multiple of 36. Also, $\displaystyle n^2+16$ must be a multiple of 4.

    So far, that tells us that $\displaystyle 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 $\displaystyle 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 $\displaystyle n^2$ ends in a 4, so $\displaystyle 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 $\displaystyle 720|(n^2(n^2+16))$ since $\displaystyle 720 = 5\cdot 3^2 \cdot 2^4$ it is equivalent to saying $\displaystyle 2^4|n^2(n^2+16)$, $\displaystyle 3^2|n^2(n^2+16)$, $\displaystyle 5|n^2(n^2+16)$.

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

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

    Finally the last case. By using the same argument as in the middle case we have $\displaystyle n=5k\pm 2$ meaning $\displaystyle n\equiv \pm 2 (\bmod 5)$ thus $\displaystyle n^2 \equiv 4 (\bmod 5)\implies n^2+16\equiv 0 (\bmod 5)$. Thus, $\displaystyle 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
    $\displaystyle 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
    11,163
    Thanks
    734
    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: Mar 1st 2010, 03:17 PM
  2. Prove divisibility
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Oct 29th 2009, 10:54 AM
  3. Prove divisibility by induction
    Posted in the Algebra Forum
    Replies: 9
    Last Post: Jun 2nd 2009, 12:14 PM
  4. Prove divisibility by 7 (using induction)
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Oct 29th 2008, 11:12 AM
  5. Prove divisibility by induction
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: Jul 30th 2008, 12:58 PM

Search Tags


/mathhelpforum @mathhelpforum