Problems & Puzzles:
Sebastián Martín Ruiz
sent the following nice puzzle:
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.
Find the first composite if it exists.
no composite is found, would it be possible to prove
that they are all one or primes?
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.
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
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.
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.
Q1 and Q2:
(53841577-1)/2243399 = 24
(174985123-1)/2243399 = 78
(14007283-1)/2334547 = 6
(70036411-1)/2334547 = 30
(16462339-1)/2743723 = 6
(65849353-1)/2743723 = 24
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.
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) =
The other two primes are given below along with GCD values:
171846th prime number p = 2334547, GCD(2^p+1,3^p+1) =
199586th prime number p = 2743723, GCD(2^p+1,3^p+1) =
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) =
323951th prime number p = 4623107, GCD(2^p+1,3^p+1) =
330026th prime number p = 4716343, GCD(2^p+1,3^p+1) =
379667th prime number p = 5482423, GCD(2^p+1,3^p+1) =
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) =
444130th prime number p = 6490151, GCD(2^p+1,3^p+1) =
Here are the first four exceptions (G = GCD(2^p + 1,3^p + 1)) :
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.
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
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.
p=2243399 and the gcd equals (78p+1)(24p+1)
p=2334547 and the gcd equals (30p+1)(6p+1)
p=2743723 and the gcd equals (24p+1)(6p+1)
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.
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
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
It's easier to start with
the following lemma.
Choose a prime p and a positive integer b; if an odd prime q
q divides b+1 or 2*p
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
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
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
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.