11
$\begingroup$

Let a and b be coprime integers. Do we know, expect, or unexpect that there are infinitely many primes p which divide

$gcd(a^{2^n} - 1, b^{2^n}-1)$

for some n? Certainly any Fermat prime will divide both if I let n get large enough, but one doesn't know whether there are infinitely many of those.

$\endgroup$
7
  • 1
    $\begingroup$ Add some hypothesis ($a,b$ multiplicatively independent?) to avoid cases like $b=a^2$. $\endgroup$ Jul 14, 2011 at 20:55
  • $\begingroup$ Also have a look at some recent papers of Corvaja and Zannier. $\endgroup$ Jul 14, 2011 at 20:58
  • 2
    $\begingroup$ @Felipe: If $b=a^2$, then the gcd is just $a^{2^n}-1$, so the problem becomes easier since Jordan is only asking about the support problem, i.e., the set of primes dividing at least one number in a sequence. And of course, in this easier case, Bang (before Zsigmondy) proved that all but finitely many terms in the sequence $a^N-1$ have a primitive prime divisor. So Support($a^{N_i}-1$) is infinite for any increasing sequence of integers $N_1,N_2,\dots$. $\endgroup$ Jul 14, 2011 at 22:39
  • 2
    $\begingroup$ Drat, I was kind of hoping Joe would know the answer to this one. $\endgroup$
    – JSE
    Jul 14, 2011 at 22:43
  • 1
    $\begingroup$ Hah! My initial impression after thinking about it for a few minutes is that it looks very hard. Even $\gcd(a^n-1,b^n-1)$ is hard, e.g., not known it equals 1 infinitely often (assuming $a$ and $b$ mult. indep.). Of course, the support problem for $\gcd(a^n-1,b^n-1)$ is trivial by Fermat's little theorem. But $2^n$ is such a sparse sequence, I don't see where to begin. Here's a question: Is the support of $\gcd(a^{n^2}-1,b^{n^2}-1)$ infinite? Follows from "infinitely many primes of the form $n^2+1$", but do we have the tools to prove this unconditionally? $\endgroup$ Jul 14, 2011 at 23:18

3 Answers 3

6
$\begingroup$

One can rewrite your problem as follows:

For $p$ prime, $p\mid a^{2^n}-1$ for some $n$ is equivalent to $\mathrm{ord}_{\mathbb{F}_p^\times}(a)$ being a power of $2$.

The probability for a random element of the multiplicative group $\mathbb{F}_p^\times$ to have order a power of $2$ is $\frac{2^n}{p-1}$ where $n$ is chosen maximal among the natural numbers $m$ with $2^m \mid p-1$.

A naive (hopefully not too naive) heuristic for the expected number of primes dividing both $a^{2^n}-1$ and $b^{2^n}-1$ for some $n$ is $-$ assuming that both conditions are independent:

$$\sum_{n\in\mathbb N}\sum_{\mbox{$p\in\mathbb{P}$ : $n$ maximal w.r.t. $p = 1 \bmod 2^n$}} \left(\frac{2^n}{p-1}\right)^2 \approx \sum_{n\in\mathbb N} \sum_{q\in\mathbb N} \frac{1}{\log(q\cdot 2^n+1)\cdot q^2}$$

For the approximation the heuristics is used that the probability for a number $m$ to be prime is about $\frac{1}{\log m}$. As the latter sum diverges one would expect that infinitely many primes divide your greatest common divisor for some $n$.

$\endgroup$
1
  • $\begingroup$ Boiling this line of thought down even further: we expect (do we?) that there are infinitely many primes of the form $p=3\cdot 2^n+1$, and the "random element" heuristic above predicts that $1/9$ of these primes will eventually divide both $a^{2^n}-1$ and $b^{2^n}-1$; this already gives infinitely many primes dividing these gcds. $\endgroup$ Jul 22, 2011 at 22:47
2
$\begingroup$

A comment on one of Joe's questions: Let $B$ be any real number. It is known unconditionally that there are infinitely many $m$ for which $\phi(m)$ is a square and for which the smallest prime factor of $m$ exceeds $B$. One can even take $m$ as a product of two primes here; see, e.g., article 4 from

http://www.integers-ejcnt.org/vol11a.html

or an arXiv preprint of Tristan Freiberg.

If we choose $B$ larger than $|a|$ and $|b|$, then $m \mid \gcd(a^{\phi(m)}-1, b^{\phi(m)}-1)$, and so there is a prime $> B$ in the support of $\gcd(a^{n^2}-1, b^{n^2}-1)$.

$\endgroup$
2
  • $\begingroup$ Well, I guess I've actually made things too hard here, since $\gcd(a^n-1, b^n-1) \mid \gcd(a^{n^2}-1, b^{n^2}-1)$; hence the support problem is trivial, again by Fermat's little theorem. I'll leave my answer up for now though. $\endgroup$ Jul 17, 2011 at 2:04
  • $\begingroup$ Good point, I guess that was as silly question. $\endgroup$ Jul 17, 2011 at 2:46
1
$\begingroup$

Just to get a feeling for what's going on here, I asked Maple for $\gcd(2^{2^n}-1,3^{2^n}-1)$ for $n=1,2,\dots,20$ and got

1 for $n=1$,

5 for $n=2,3$,

$85=5\cdot17$ for $n=4,5,6,7$,

$21845=5\cdot17\cdot257$ for $n=8,\dots,15$,

$1431655765=5\cdot17\cdot257\cdot65537$ for $n=16$ to $n=19$, all pretty much as expected, then

$19515599812384085=5\cdot17\cdot257\cdot65537\cdot13631489$ for $n=20$.

The first few results are as expected from the question statement, as 5, 17, 257, and 65537 are Fermat primes. 13631489 is a factor of a Fermat number.

$\endgroup$
16
  • $\begingroup$ Of course, each term is divisible by the previous term. A slightly harder, but maybe more natural, question, would be the set of primes dividing some term in the sequence $\gcd(2^{2^n}+1,3^{2^n}+1)$. More generally, some subsequence of $\gcd(\Phi_N(2),\Phi_N(3))$, where~$\Phi_N$ is the cyclotomic polynomial. In this case, we're taking $N=2^n$ for $n=1,2,3,...$. $\endgroup$ Jul 15, 2011 at 0:59
  • $\begingroup$ It seems that $\gcd(2^{2^n}+1,3^{2^n}+1)$ is 5 for $n=1$ and 1 for $2\le n\le20$. $\endgroup$ Jul 15, 2011 at 1:12
  • $\begingroup$ @Gerry: Do you want to conjecture it's 1 for all $n\ge2$? Here's an amusing example. Consider the sequence $A_n=\gcd(2^n+3^n+1,2^n+7^n+2)$. I checked that $A_n=1$ for all $n\le5000$. Further, the support of the sequence $(A_n)$ contains no primes smaller than 5000. Challenge: Prove that $A_n=1$ for infinitely many $n$. I have no idea how to begin to attack this, nor the easier(?) case of a function field analogue over $\mathbb{C}[T]$. For $\mathbb{C}[T]$, Ailon and Rudnick prove (under suitable hypotheses) that $\gcd(a(T)^n-1,b(T)^n-1)=1$ for lots of $n$. $\endgroup$ Jul 15, 2011 at 2:43
  • 1
    $\begingroup$ @Joe, I am far too timid to make a conjecture based on $2\le n\le20$. A bit closer to the ground, Ilan Vardi found $\gcd(n^7+19,(n+1)^7+19)=1$ for $n\lt8424432925592889329288197322308900672459420460792433$ but the equality fails for the next $n$. $\endgroup$ Jul 15, 2011 at 5:58
  • $\begingroup$ @Gerry $\gcd(2^{2^n}+1,3^{2^n}+1)=1$ for $2 \le n \le 29$. Took about 30 minutes with ntl (up to 28 took 15 minutes in sage). $\gcd(2^{2^n}-1,3^{2^n}-1)=19515599812384085$ for $20 \le n \le 29$. $\endgroup$
    – joro
    Jul 15, 2011 at 10:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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