4
$\begingroup$

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 ).

I also had the impression

$$\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 using p-adics help ?

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

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

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

$\endgroup$
  • $\begingroup$ $p=107$ gives the next counter example, where the gcd is $643$. $\endgroup$ – alex.jordan Nov 14 '15 at 22:13
  • $\begingroup$ That is nice. Thanks. How about Some theory ? Is it provable that there are only a finite amount of counterexamples ? $\endgroup$ – mick Nov 14 '15 at 22:18
  • $\begingroup$ @mick I can't offer theory, but I added a simple Sage command to compute the gcds. $\endgroup$ – alex.jordan Nov 14 '15 at 22:23
  • $\begingroup$ 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)? $\endgroup$ – A.P. Nov 14 '15 at 23:57
  • 1
    $\begingroup$ @A.P. No reason, just a lack of better familiarity with Sage. $\endgroup$ – alex.jordan Nov 15 '15 at 0:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.