Problems & Puzzles: Puzzles

Puzzle 1087 (p^2-1)/24=q... JM Bergot sent the following nice puzzle For any three primes p>q>r, there can be (p^2-1)/24=q AND (q^2-1)/24=r? Q1. Find several examples, if any? Q2. Is there a longer chain?

---

Durig the week from May 21 to May 27, contributions came from Adam Stinchcombe, Fred Schneider, Emmanuel Vantieghem, Seongjae Choi,  Jeff Heleen, Giorgos Kalogeropoulos, Gennady Gusev.

***

Adam wrote:

The only possibility is p=13, q=7, r=2.
 

Suppose (p^2-1)/24 is an integer and factor 24 as g*h so that both (p-1)/g and (p+1)/h are both integers.  If p is sufficiently large then [(p-1)/g]*[(p+1)/h] is a factorization of (p^2-1)/24 and each factor is bigger than 1 so (p^2-1)/24 is composite.  Checking small primes, p=7,11,and 13 are the only candidates.

 

***

Fred wrote:

Consider p^2 -1 = (p -1) * (p+1) for prime p

After p = 2, this will always be a product of even numbers.
After p = 3, this will always be a product of even composite numbers.

When can (p^2 -1) / 24 be prime?

Consider p-1, p, p + 1 where p is a prime > 3 and of course odd.  Thus, p-1 and p+1 are even.

Among 3 consecutive integers, one must be divisible by 3.  Because p is a prime > 3, either p -1 or p +1 must be divisible by 3.
p-1 and p+1 are consecutive even numbers.  Among consecutive even numbers, one must be divisible by 2, the other by 4.
Note that 24 = 3 * 2 * 4

Let a = p-1 and b = p + 1 (Note that a/2 and b/2 are relatively prime to each other)
Divide ab by 24.

Let a' = a / gcd(a, 24)
Let b' = b / gcd(b, 24)
 
Let's call the second prime candidate q = (p^2-1)/24 = a' * b'

For q to be prime, then either a' or b' must be 1.
In order for a' or b' to be 1, a or b respectively must be a divisor of 24.

So, we only need to check a small number of possible candidates.
The upper bound is n -1 = 24 = 25

The only primes p such that (p^2 -1 ) / 24 are 7 (mapping to 2), 11 (mapping to 5) and 13 (mapping to 7)

So, (13, 7, 2) is the only triple and there are no longer chains

***

Emmanuel wrote:

First, let's denote  (m^2 - 1)/24  by  F(m).

There is only one "chain" : (p, q, r) = (13, 7, 2).

Indeed, the only natural numbers  m  for which  (m^2 - 1)/24  is an integer are those of the form
24x + 1, 5, 7, 11, 13, 17, 19, 23.
Thus, we have :
   F(24x + 1) = (24^2 x^2 + 48x) / 24 = 24 x^2 + 2 x, always even, > 2.
   F(24x + 5) =... = 24 x^2 + 10 x + 1 = (6 x + 1) (4 x + 1), never prime.
   F(24x + 7) = ... = 24 x^2 + 14 x + 2, anever prime unless  x = 0.
   F(24x + 11) = ... = 24 x^2 + 22 x + 5 = (12 x + 5) (2 x + 1), never prime unless  x = 0.
   F(24x + 13) = ... = 24 x^2 + 26 x + 7 = (12 x + 7) (2 x + 1), never prime unless  x = 0.
   F(24x + 17) = ... = 24 x^2 + 34 x + 12, always even, > 2.
   F(24x + 19) = ... = 24 x^2 + 38 x + 15 = (6 x + 5) (4 x + 3), never prime.
   F(24x + 23) = ... = 24 x^2 + 46 x + 22  always even > 2.
So, F(m) is prime only when  m = 7, 11 or 13.

 

 

****
Seongjae wrote:

p>q

(p^2-1)/24=q
-> p = sqrt( 24*q + 1 )
-> so if q>24, p<q and this contradicts the assumption.
-> so q<=24 or we can just ignore the inequality assumption.

 

(p^2-1)/24=q
 

-> (p+1)(p-1) = 24q
we have assumed that q is prime.
so the right side only can be factored by...
1 x 24q   -> either (p+1 = 1) or (p-1 = 1) -> p = 0 or 2
2 x 12q   -> either (p+1 = 2) or (p-1 = 2) -> p = 1 or 3
3 x 8q     -> either (p+1 = 3) or (p-1 = 3) -> p = 2 or 4
4 x 6q     -> either (p+1 = 4) or (p-1 = 4) -> p = 3 or 5
6 x 4q     -> either (p+1 = 6) or (p-1 = 6) -> p = 5 or 7
8 x 3q     -> either (p+1 = 8) or (p-1 = 8) -> p = 7 or 9
12 x 2q   -> either (p+1 = 12) or (p-1 = 12) -> p = 11 or 13
24 x q     -> either (p+1 = 24) or (p-1 = 24) -> p = 23 or 25

but we also have assumed that p is prime.
so the only possible numbers that can be p are
2, 3, 5, 7, 11, 13, 23.

and q = (p^2-1)/24 for each p is
q = 1/8, 1/3, 1, 2, 5, 7, 22. and these should be prime

so there are only (p, q) = (7, 2), (11, 5), (13, 7)

So the p,q,r pair is unique and that is
p, q, r = 13, 7, 2
 

 

Q1. only (13, 7, 2)

Q2. No other (or longer) chain exists. 

 

***

Jeff wrote:

Up to 10^9 I found only p = 13, q = 7, r = 2.

***

Giorgios wrote:

It is well known that if p is prime then (p^2-1) is always divisible by 24.

In fact this is true for any p not divisible by 6.

So, (p^2-1) = (p-1)(p+1) has always 2, 2, 2 and 3 as factors.

Also, p-1 and p+1 are always even for any p prime >2.

In order (p^2-1)/24 to be prime, it must be of the form (p^2-1) = 2*2*2*3*S where S is prime.

Here are the only possible ways we can distribute these factors between the even numbers p-1 and p+1

 

   p-1     |    p+1    |     extra factor S

------------------------------------------------------------

   2        |   2*2*3  |     p-1=2*5 and S=5

   2*2     |   2*3     |             ------

   2*3     |   2*2     |     p+1=2*2*2 and S=2

   2*2*3 |     2       |     p+1=2*7  and  S=7

 

For any other prime S, the difference between p-1 and p+1 will be bigger than 2.

In conclusion, the only prime values of (p^2-1)/24 are 2, 5 or 7 and this happens for p equal to  7, 11 and 13 respectively. 

The only possible chain is p=13 -> q=7 -> r=2.

For more insights in this problem, visit A024702

***

Gennady wrote:

We need to find 3 primes forming a chain.

Let p be a prime. Find q.

p can be of the form 12*k+n, where n=1,5,7 or 11.

Then

q=(12*k+1)^2-1)/24=k*(6*k +1), q is prime if k=1 -> q=7, p=13, otherwise composite;

q=(12*k+5)^2-1)/24=(2* k + 1)*(3*k + 1), for k>0 q is a composite;

q=(12*k+7)^2-1)/24=(3* k + 2)*(2*k + 1), for k=0 -> q=2, p=7, otherwise composite;

q=(12*k+11)^2-1)/24=( k + 1)*(6*k + 5), for k=0 -> q=5, p=11, otherwise composite;

 

So there is only one chain 13, 7, 2.

 

***

 

 

***