Which is the greatest possible natural number that divides $(p+3)(p-7)$, where $p$ is a prime number greater than $3$?

Question

Which is the greatest possible natural number that definitely divides $(p+3)(p-7)$, where $p$ is a prime number greater than $3$?

This one is from my module, comes as a fill in the blanks with no answer. I have a feeling that there is something wrong with this question, since for $p=5$, one has $(p+3)(p-7)=-16$.

---

ADDED:

As mentioned, in one answer I tried substituting $p=5,7,9,11,13,17,19,...$ and spotted that the greatest number is $8$. I am just wondering .. is there any other way (probably using modulus) to directly find this number without actually substituting ?

Answer 1

I have a feeling that there is something wrong with this question

The "greater than $3$" condition is a bit strange, because the answer is unchanged if $p=3$ is allowed. And if they wanted to exclude negative values of $(p+3)(p-7)$, they should say "greater than 7". But the question as it stands is technically correct. It would perhaps be better like this:

Which is the greatest natural number that divides $(p+3)(p−7)$ for every odd prime number $p$?

If $p$ is odd, then $p = 2k+1$ for some $k$. So $(p+3)(p-7) = (2k+4)(2k-6) = 4(k+2)(k-3)$, which is divisible by $8$ since one of $k+2, k-3$ must be even. So $8$ divides $(p+3)(p−7)$ for every odd prime number $p$.

That's half the question. The other half is to show that no natural number $n > 8$ divides $(p+3)(p−7)$ for every odd prime number $p$. Note that if $n$ has this property, then so does every factor of $n$. So it is enough to show that (i) $16$ doesn't have this property; and (ii) no odd prime $q$ has this property.

To show that $16$ doesn't have this property, just put $p=11$. So suppose now that $q$ is an odd prime. We need to produce another odd prime $p$ that is not equal to $q-3 \pmod q$ and not equal to $7 \pmod q$. Then we can be sure that $q$ doesn't divide $(p+3)(p-7)$. It seems a bit like overkill to me, but we can use Dirichlet's theorem on arithmetic progressions for this: for coprime $a$ and $q$, the arithmetic progression $a + rq$ $(r = 0, 1, 2,...)$ contains infinitely many primes. So we just have to choose $a$ with $1 \le a \le q-1$ that is not equal to $q-3 \pmod q$ and not equal to $7 \pmod q$. If $q=3$, we can choose $a=2$; and if $q \ne 3$, we can choose $a=3$.

And we're done.

Answer 2

There's nothing wrong with the question.

You're looking for a natural number. You know it divides $(p+3)(p-7)$. And you can put in some primes into that equation, as you have done already - you've got $-16$. What happens if you stick in $p=11$? Or $p=13$?

OK, now you've identified the natural number. Can you see why the product is always divisible by that number?

clue word: modulo

Answer 3

Hint $\ \rm\:d\ |\ f_p = (p\!+\!3)(p\!-\!7)\ \Rightarrow\ d\ |\ f_5,\:f_7,f_{11} =\:\! -16,0,56\ \Rightarrow\ d\ |\ gcd(16,56) = 8$. Conversely $\!\bmod 8\!:\ \color{#c00}{{\rm odd}^2} \equiv 1\Rightarrow \rm\ f_p\equiv (p\!+\!3)(p\!+\!1)\: \equiv\: \color{#c00}{p^2}\!+\!4p+3 \:\equiv\: 4(p\!+\!1) \equiv 0$.

Generally: for a sequence satisfying a monic $\rm n$'th order linear recurrence with integer coefficients one easily proves by induction that the gcd of all terms is the gcd of the first $\rm\,n\,$ terms, since successive terms are integer linear combinations of the first $\rm\,n\,$ terms so they don't change the gcd.

Answer 4

If $p$ is prime it can be written $p=4a+1$ or $p=4a+3.$

Substituting the first of these gives
$$(p+3)(p-7)=p^2-4p-21 = 16a^2+8a+1-16a-4-21 = 16a^2-8a-24 = 8(2a^2-a-3)$$
and the other gives $$(p+3)(p-7)=p^2-4p-21 = 16a^2+24a+9-16a-12-21 = 16a^2+8a-24 = 8(2a^2+a-3)$$
and so $(p+3)(p-7)$ is divisible by $8$ either way.

Edit
To show that 8 is the largest such divisor, we must show that $2a^2-a-3$ is not divisible by the same prime for all values of $a$. Setting $a=4\text{ and }5$ produces 25 and 42 respectively which have no prime factors in common.

And we must also show that $2a^2+a-3$ is not divisible by the same prime for all values of $a$. Setting $a=4\text{ and }5$ again produces 33 and 52 respectively which also have no prime factors in common.

Answer 5

Observe that $(5+3)(5-7) = -16$ and $(11+3)(11-7) = 56$; these have greatest common multiple 8. So the answer must be some factor of 8. If you keep trying more numbers you'll see it looks to be 8.

How to prove it? $p$ is odd. So $p+3$ and $p-7$ are even numbers which differ by 10. Let $p = 2n+7$; then we want to show that for any integer $n$, $2n(2n+10)$ is divisible by 8. But we can rewrite this as $4n(n+5)$, so we just need to show that $n(n+5)$ is always even; either $n$ is even or $n+5$ is.

A challenge for you, to help you understand what's going on here: prove in a similar way that for every integer $n$, $n^3-n$ is a multiple of 6 and $n^5-n$ is a multiple of 30.

Answer 6

If p is odd number, p-7 is even =2k(say). Then (p+3)(p-7)=(2k+10)2k=8k(k+1)/2+16k, is clearly divisible by 8 for all integral value of k.

Now if f(k) = (2k+10)2k=4k(k+5), f(k+1)= 4(k+1)(k+6) (f(k),f(k+1))=(4k(k+5), 4(k+1)(k+6))= 4(k(k+5), (k+1)(k+6)) =4(k(k+5), (k+1)(k+6) - k(k+5)) as (a,b)=(a, b-a) =4(k(k+5), 2k+6) =8(k(k+5)/2, k+3) as k(k+5)/2 is integer for all integral value of k.

Now, 2 k(k+5)/2 - k(k+3)= 2k. We know ax+by=c is solvable iff (a,b)|c where a,b,c,x,y are integers. Here, x=2, a=k(k+5)/2, y=k, b=k(k+3), c=2k So, (k(k+5)/2, (k+3)) | 2k, =>2|(k+3) =>k is odd. For even k, 2∤(k(k+5)/2, (k+3)). In that case, no natural number>1, can divide f(k) for all integral value of k. So, 8 will be the greatest natural number that divides (p+3)(p-7) for all odd integral value of p.

Answer 7

I would interpret the question as, "What is the greatest natural number that divides $(p+3)(p-7)$ for all primes $p>3$?"

We can write $(p+3)(p-7)=4\cdot\frac{p+3}2 \cdot\frac{p-7}2$ but one of the latter two factors is even, since they differ by five, an odd number, so we can conclude that $(p+3)(p-7)$ is always divisible by eight, but $(5+3)(5-7)=-16$, $(9+3)(9-7)=24$, and $\gcd(-16,24)=8$. Therefore no natural number larger than eight divides $(p+3)(p-7)$ for all primes $p>3$, and eight is in fact the greatest natural number that divides $(p+3)(p-7)$ for all primes $p>3$.

Answer 8

The question is sloppily phrased, because to me it reads more like "Which is the greatest possible natural number that definitely divides $(p+3)(p−7)$, where $p$ is some given prime greater than 3?", in which case the answer is trivially $(p+3)(p-7)$ !

But I imagine (as does everyone else by the look of it) the OP meant "Which is the greatest possible natural number that definitely divides $(p+3)(p−7)$ for every prime $p$ greater than 3?"