Problems & Puzzles: Puzzles

Puzzle 1073 p*q=1+k^2 Sebastián Martín Ruiz, sent the following nice puzzle: Q1 . Prove that for any two consecutive primes p<q there is not an integer k value such that p*q=1+k^2, or give a counterexample. Q2. Redo Q1, but for the smallest pair of two primes, p<q, not necessarily consecutive.

---

During the week 22-28 Jan, 2022, contributions came from Alain Roccelli, Giorgos Kalogeropoulos, Emmanuel Vantieghem

***

Alain wrote:

Let 2*d=q-p and 2*m=p+q where p, q are primes with p<q

Also p=m-d, q=m+d and p*q=m^2-d^2

If m^2-d^2=k^2+1 we deduce m>k and note h=m-k  (with integer h >0)

We get the relation :

p*q = (k+h)^2-d^2 = k^2+2*h*k+h^2-d^2 = k^2+1

also h^2+2*k*h-(d^2+1) = 0

This binomial formula with h as a variable admits integer roots only if the reduced discriminant is a square.

We get k^2+d^2+1 is a square and its minimum value is (k+1)^2 = k^2+2*k+1

In this case : 2*k = d^2

Because k is integer we deduce d is an even integer.

Except for d = 4 we can prove that d is a multiple of 10.

Indeed,if d ends in 2, 4, 6 or 8 then k^2 = (d^2/2)^2 ends in 4.

If k^2+1 ends in 5 then p*q is divisible par 5 (which is irrelevant for the present problem).

Using the previous considerations, I got the following results :

5*13 = 8^2+1 ; d=4
41*61 = 50^2+1 ; d=10
1201*1301 = 1250^2+1 ; d=50
1741*1861 = 1800^2+1 ; d=60
2381*2521 = 2450^2+1 ; d=70
9661*9941 = 9800^2+1 ; d=140
14281*14621 = 14450^2+1 ; d=170
19801*20201 = 20000^2+1 ; d=200
23981*24421 = 24200^2+1 ; d=220
100801*101701 = 101250^2+1 ; d=450
105341*106261 = 105800^2+1 ; d=460
134681*135721 = 135200^2+1 ; d=520
161881*163021 = 162450^2+1 ; d=570

          and so on ...

I send you an additional information :

m = (p+q)/2 must be greater than k. Also we deduce the smallest pair, p<q, is obtained when m is equal to k+1 (h=1).

Because of Cramer 's conjecture { p_n+1 - p_n < [log(p_n)]^2 }, pairs p, q cannot be consecutive primes.

We can notice that values p, q are included in the sequence OEIS A027862 and  correspond to the consecutive numbers ending in 1 and satisfying the equality :

(p+q)/2 = SQRT(p*q-1) + 1  with SQRT() as square root of ()

***

Giorgos wrote:

If k^2+1=p*q with p<q then we can investigate the minimum difference p-q as k grows and compare it

with the maximum prime gap given by Firoozbakht's conjecture: g_n < (log p_n)^2 - log p_n.
 

Conjecture: If k>n then the minimum difference p - q for every k>n is approximated by pi^(log_10(n) + 1)

Here are some results 

 

	min( p - q )	pi^(log_10(n)+1)	max gap
n	for k>n	Conjecture	Firoozbakht	p	k
10^2	20	31	10	41	50
10^3	100	97	43	1201	1250
10^4	340	306	81	14281	14450
10^5	900	961	121	100801	101250
10^6	2840	3020	177	1006781	1008200
10^7	9380	9488	246	10993361	10998050
10^8	28320	29809	320	100238641	100252800
10^9	90040	93648	409	1013355181	1013400200
10^10	284780	294204	507	10137313661	10137456050

 

As we can see the min p-q for k>n grows much faster than the max prime gap.

This is why I believe that those consecutive primes p and q do not exist.

Unfortunately, I don't have a proof for any of these conjectures.

 

For Q2, the smallest pairs >n can be easily found from the table above.

{41,61},{1201,1301},{14281,14621},{100801,101701},{1006781,1009621},{10993361,11002741},{100238641,100266961},{1013355181,1013445221},{10137313661,10137598441}

***

Emmanuel wrote:

Q1. Trivial check learns that  p > 2.
If   p, q  are odd primes such that  p*q = 1 + k^2, then  p  and  q  must be both of the form  4m + 1.
Thus, we can say : q = p + 4t, for some  t > 0
From  p(p + 4t) - 1 = k^2  it then follows :
p^2 + 4 p t - 1 = (p + 2t)^2 - 4t^2 - 1 = k^2 <= (p+2t - 1)^2,
which implies : 2p <= 4t^2 - 4t +2 = (2t - 1)^2 + 1.
Thus, q - p = 4t >2* Sqrt(2p - 1).
This would contradict Andrica's conjecture ( g(n) < 2*Sqrt(p(n) + 1 )   which, as far as I know, is still not proved.
Q2.
5*13 = 65 = 1 + 8^2.

***

Jim Howell wrote on Jan, 29, 2022:

The other solvers seem to have missed the smallest solution for Q2, which is:

 

2*5 = 3^2+1

 

The next smallest solution is:

 

2*13 = 5^2+1

 

***