# Math Help - Prove divisibility

1. ## 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.

2. anyone?

3. As well as being an even number, n has to be a multiple of 3 (otherwise one of the numbers n–1 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 36×4=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).

4. 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 .

5. 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

6. Originally Posted by bobak
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