Problems & Puzzles: Puzzles

Puzzle 1064 GCD(2^p+1,3^p+1) Sebastián Martín Ruiz sent the following nice puzzle: I have checked that GCD(2^p+1,3^p+1) is one or prime for the first 60,000 prime numbers. Q1. Extend the verification as far as possible. Q2. Find the first composite if it exists. Q3 if no composite is found, would it be possible to prove that they are all one or primes? Q4. Prove that GCD(2^p+1,3^p+1) mod p=1 for all p.

---

During the week 20-26 Novembre, 2021, contributions came from Giorgos Kalogeropoulos, Adam Stinchcombe, Simon Cavegn, Shyam Sunder Gupta, Emmanuel Vantieghem, Jan van Delden, Oscar Volpatti.

***

Giorgos wrote:

Q2. The first three counterexamples are for primes p: 2243399, 2334547 and 2743723

In these cases we get GCD 9421474973858971, 981019829181313 and 1084034372016667 respectively which are all composites.

 

Q4. If GCD(2^p+1, 3^p+1) = P1*P2*...Pn then it seems that all primes Pn are of the form 6kp+1. So, P1-1, P2-1, ...Pn-1 are all divisible by p.

This means that Pn=1 mod p for all factors of GCD. I don't have a proof of the above statement but if it is true, then it is easy to show that GCD(2^p+1, 3^p+1) mod p = 1.

***

Adam wrote:

Q4. Suppose q is a prime common divisor of 2^p+1 and 3^p+1.  Then gcd(q,6)=1 and q divides 3^p-2^p = (3^p+1)-(2^p+1).  So 3^p-2^p=0 mod q, 3^p=2^p mod q and (3/2)^p=1 mod q.  So the order of 3/2 mod q is a divisor of p and so is equal to p.  The order of any non-zero number mod q is a divisor of q-1 so p divides q-1 and q is 1 mod p.

***

Simon wrote:

Q1 and Q2:
Composite: gcd=9421474973858971=53841577*174985123, p=2243399
Composite: gcd=981019829181313=14007283*70036411, p=2334547
Composite: gcd=1084034372016667=16462339*65849353, p=2743723

Noticed:
(53841577-1)/2243399 = 24
(174985123-1)/2243399 = 78

(14007283-1)/2334547 = 6
(70036411-1)/2334547 = 30

(16462339-1)/2743723 = 6
(65849353-1)/2743723 = 24

Conjecture:
GCD(2^p+1,3^p+1) has only prime factors of the form 6*p*n+1, n is a natural number or zero.

***

Shyam wrote:

Q1, Q2 and Q3:
The verification was extended for the first 200,000 prime numbers.
I found three prime numbers p such that GCD(2^p+1,3^p+1) is composite. The smallest of these three
prime numbers is 165627th prime number 2243399. For this prime p=2243399, GCD(2^p+1,3^p+1) =
9421474973858971 =53841577*174985123
The other two primes are given below along with GCD values:
171846th prime number p = 2334547, GCD(2^p+1,3^p+1) = 981019829181313 =14007283*70036411
199586th prime number p = 2743723, GCD(2^p+1,3^p+1) = 1084034372016667=16462339*65849353

In continuation to my email dated 21st Nov 2021, the verification was extended further up to 400,000
prime numbers and I found four more prime numbers p such that GCD(2^p+1,3^p+1) is composite. These four
prime numbers are given below along with GCD values:

278740th prime number p = 3932207, GCD(2^p+1,3^p+1) = 2226564390248467
=23593243*94372969
323951th prime number p = 4623107, GCD(2^p+1,3^p+1) = 6924890617423897
=27738643*249647779
330026th prime number p = 4716343, GCD(2^p+1,3^p+1) = 7207021062122857
=28298059*254682523
379667th prime number p = 5482423, GCD(2^p+1,3^p+1) = 5410253348534449
=32894539*164472691

Later, on Dec 5, 2021, he added:

In continuation to my email dated 24th Nov 2021, the verification was extended further up to 480,000
prime numbers and I found two more prime numbers p such that GCD(2^p+1,3^p+1) is composite. These two
prime numbers are given below along with GCD values:

412433th prime number p = 5993411, GCD(2^p+1,3^p+1) = 6465775790448577
=35960467*179802331
444130th prime number p = 6490151, GCD(2^p+1,3^p+1) = 68237738995819297
=38940907*1752340771

 

***

Emmanuel wrote:

Here are the first four exceptions  (G = GCD(2^p + 1,3^p + 1)) :

 

     p                           G                     factorization of G
2243399    9421474973858971 = 53841577*174985123
2334547    981019829181313 = 14007283*70036411
2743723    1084034372016667 = 16462339*65849353
3932207    2226564390248467 = 23593243*94372969

I think there may be infinitely many.

Q4.
If  q  (> 3) is a prime factor of  2^p + 1, then we have : 2^(2p) == 1 (mod q).
This implies that the (multiplicative) order of  p  mod q  is equal to  2p, which means that the smallest positive integer  x  such that  2^x == 1 (mod q)  is  2p.
It follows from this that if  y  is a positive integer such that  2^y ==1 (mod q), y will be a multiple of  2p.

Since  2^(q - 1) == 1 (mod q)  (Little Fermat) we have : q == 1 (mod p).
Thus, all prime divisors  (and hence all divisors) of  2^p + 1  are == 1 (mod p).
The same argument (mutatis mutandis) applies for  3^p + 1, so that we may say that the greatest common divisor of  2^p + 1  and  3^p + 1  is of the form  p m + 1, QED.
 

***

Jan wrote:

Q2

 

p[165627]=2243399 and the gcd equals (78p+1)(24p+1)
p[171846]=2334547 and the gcd equals (30p+1)(6p+1)

p[199586]=2743723 and the gcd equals (24p+1)(6p+1)

 

Q4 

 

For p=2 we find gcd(5,10) mod 2=1.
For p=3 we find gcd(9,28) mod 3=1.

 

If gcd(a,q)=1 and a^n=-1 mod q with q prime then a^(2n)=1 mod q; the order of a mod q=2n. By Fermat’s little theorem we have 2n|q-1.
The above applies if we choose a=2,a=3,n=p, q>3 prime. We found q=1 mod 2p, in particular q=1 mod p. Every prime divisor of the gcd has this form, hence the gcd itself as well.
[And we may rule out q=2, q=3].

 

If fact I strongly feel that one should have q=1 mod 6p, for which one needs to prove that 3|q-1 as well.

 

***

Oscar wrote:

For brevity, let's define function G(n) = GCD(2^n+1,3^n+1).
G(p) is one or prime for the first 165626 primes, then we find a semiprime:
G(2243399) = 53841577*174985123.

 

Question Q4 asked to prove the following statement: 

for all p, G(p) is congruent to 1 modulo p.

But we can actually prove a stronger statement:

for all p, any prime factor of G(p) is congruent to 1 modulo p.

 

It's easier to start with the following lemma.
Choose a prime p and a positive integer b; if an odd prime q divides b^p+1, then either q divides b+1 or 2*p divides q-1.
Prime q must be coprime with b, otherwise q divides b^p but not b^p+1; let x be the multiplicative order of b modulo q.

By Fermat's little theorem,  b^(q-1) == 1 mod q,  so x divides q-1.
 

By hypothesis,  b^p == -1 mod q,  so  b^(2*p) == 1 mod q  and x divides 2*p too.

If x = 1 or x = p, then b^p == 1 mod p, contradicting hypothesis; hence x = 2 or x = 2*p.

As q is prime, b has order x = 2 only if b == -1 mod q, so that q divides b+1.

Otherwise b must have order x = 2*p, so 2*p divides q-1.

Main theorem.

Prime 2 is coprime with 2^p+1 and prime 3 is coprime with 3^p+1, so any prime factor q of G(p) must be greater than 3. Such q divides neither 2+1=3 nor 3+1=2^2, so it must be of the form 2*p*k+1.

 

This result is the base for a fast composite-seeking algorithm.

Pick odd primes q in increasing order; for each prime factor p of q-1, check if the following modular equalities both hold:

2^p == -1 mod q

3^p == -1 mod q

If so, then q is a prime factor of G(p): store the pair (q,p). Finding two or more pairs with the same value p ensures that such G(p) is composite.

***