Greatest common divisor of a^{2^n}-1 and b^{2^n}-1 - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T12:48:31Z http://mathoverflow.net/feeds/question/70371 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/70371/greatest-common-divisor-of-a2n-1-and-b2n-1 Greatest common divisor of a^{2^n}-1 and b^{2^n}-1 JSE 2011-07-14T20:42:09Z 2011-07-17T01:45:47Z <p>Let a and b be coprime integers. Do we know, expect, or unexpect that there are infinitely many primes p which divide</p> <p>$gcd(a^{2^n} - 1, b^{2^n}-1)$</p> <p>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.</p> http://mathoverflow.net/questions/70371/greatest-common-divisor-of-a2n-1-and-b2n-1/70389#70389 Answer by Gerry Myerson for Greatest common divisor of a^{2^n}-1 and b^{2^n}-1 Gerry Myerson 2011-07-15T00:31:42Z 2011-07-15T00:31:42Z <p>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 </p> <p>1 for $n=1$, </p> <p>5 for $n=2,3$, </p> <p>$85=5\cdot17$ for $n=4,5,6,7$, </p> <p>$21845=5\cdot17\cdot257$ for $n=8,\dots,15$, </p> <p>$1431655765=5\cdot17\cdot257\cdot65537$ for $n=16$ to $n=19$, all pretty much as expected, then </p> <p>$19515599812384085=5\cdot17\cdot257\cdot65537\cdot13631489$ for $n=20$. </p> <p>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. </p> http://mathoverflow.net/questions/70371/greatest-common-divisor-of-a2n-1-and-b2n-1/70420#70420 Answer by jp for Greatest common divisor of a^{2^n}-1 and b^{2^n}-1 jp 2011-07-15T10:51:30Z 2011-07-16T13:15:19Z <p>One can rewrite your problem as follows:</p> <p>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$.</p> <p>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$.</p> <p>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:</p> <p>$$\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}$$</p> <p>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$.</p> http://mathoverflow.net/questions/70371/greatest-common-divisor-of-a2n-1-and-b2n-1/70534#70534 Answer by Anonymous for Greatest common divisor of a^{2^n}-1 and b^{2^n}-1 Anonymous 2011-07-17T01:45:47Z 2011-07-17T01:45:47Z <p>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 </p> <p><a href="http://www.integers-ejcnt.org/vol11a.html" rel="nofollow">http://www.integers-ejcnt.org/vol11a.html</a></p> <p>or an arXiv preprint of Tristan Freiberg.</p> <p>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)$. </p>