# Why is $\gcd(2^p + 1,3^p + 1) = 1$?

Let $$p$$ be an odd prime. Why is $$\gcd(2^p + 1,3^p + 1) = 1$$ ?

I tried using Fermat's little and $$\gcd(a+b,a) = \gcd(a,b)$$ but without success.

I can make a statistical argument that suggests there are only a finite number of solutions.

But I do not like to use statistics in number theory. It has a bad reputation. ( example naive probably for Fermat primes vs Mersenne primes ).

$$\gcd(2^{5n} + 1,3^{5n} + 1) = 1$$

For most positive integers $$n$$.

Im not sure if it helps but we can remove a few factors to arrive at

$$\gcd(\frac{2^p + 1}{3},\frac{3^p + 1}{4}) = 1$$

Would it have value as an additional primality test in combination with Fermat's primality test ?

• How do you know the statement in question is in fact true? – Noah Schweber Nov 14 '15 at 21:50
• $\mathrm{gcd}\,(2^{83}+1, 3^{83}+1) = 499$. There are many other (larger) solutions. – rogerl Nov 14 '15 at 22:05

A CAS tells me $$\gcd(2^{83}+1,3^{83}+1)=499$$ So the claim is false. It happens to be true for many primes $p$, but that is just because of the abundance of possible divisors available for large numbers like $2^{p}+1$ and $3^{p}+1$, and the consequent unlikelihood of an overlap. And yet it's not impossible to have overlap, as with $p=83$.

(Looks like @rogerl beat me to the counter example in the comments.)

This Sage code lists all the primes less than the $N$th prime where the $\gcd$ is larger than $1$:

N=1000
for k in range(N):
if (gcd(2^Primes().unrank(k)+1,3^Primes().unrank(k)+1) != 1):
print(Primes().unrank(k))


You can enter this here, for instance: https://sagecell.sagemath.org

• $p=107$ gives the next counter example, where the gcd is $643$. – alex.jordan Nov 14 '15 at 22:13
• That is nice. Thanks. How about Some theory ? Is it provable that there are only a finite amount of counterexamples ? – mick Nov 14 '15 at 22:18
• @mick I can't offer theory, but I added a simple Sage command to compute the gcds. – alex.jordan Nov 14 '15 at 22:23
• Just out of curiosity, is there any particular reason why you used the Primes().unrank method instead of, say, for k in prime_range(N)? – A.P. Nov 14 '15 at 23:57
• @A.P. No reason, just a lack of better familiarity with Sage. – alex.jordan Nov 15 '15 at 0:03