Composite pairs of the form n!-1 and n!+1 - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T07:03:29Z http://mathoverflow.net/feeds/question/30101 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/30101/composite-pairs-of-the-form-n-1-and-n1 Composite pairs of the form n!-1 and n!+1 François G. Dorais 2010-06-30T19:43:40Z 2010-08-31T15:03:39Z <p>It's well known that the numbers of the form $n!\pm1$ are not always prime. Indeed, <a href="http://en.wikipedia.org/wiki/Wilson%27s_theorem" rel="nofollow">Wilson's Theorem</a> guarantees that $(p-2)!-1$ and $(p-1)!+1$ are composite for every prime number $p > 5$. </p> <blockquote> <p>Is there a proof, preferably an elementary proof, that there are infinitely many composite <em>pairs</em> of the form $n!\pm1$?</p> </blockquote> <p>The motivation for this question comes from my answer to <a href="http://mathoverflow.net/questions/30064/are-the-types-of-nonstandard-natural-numbers-within-a-z-chain-identical" rel="nofollow">this recent question</a>. There, I show that every nonstandard model of Peano Arithmetic has a $\mathbb{Z}$-chain consisting entirely of composite numbers. The example I gave is that of a $\mathbb{Z}$-chain contained in the infinite interval $[N!+2,N!+N]$, where $N$ is any nonstandard natural number. I wonder if I could have picked some $\mathbb{Z}$-chain centered at $N!$ instead. A positive answer to the above question would mean that this is indeed possible. Note that it is important in this context that the proof is elementary, but I will also accept beautiful analytic arguments.</p> <p>Andrey Rekalo pointed out that $(N!)^3 \pm 1$ are both composite. This means that, if $N$ is a nonstandard integer, then the $\mathbb{Z}$-chain centered at $(N!)^3$ has only composite numbers all but two have standard factors. I don't know if it's possible to find a $\mathbb{Z}$-chain all of whose elements have a standard factor.</p> http://mathoverflow.net/questions/30101/composite-pairs-of-the-form-n-1-and-n1/30177#30177 Answer by Andrey Rekalo for Composite pairs of the form n!-1 and n!+1 Andrey Rekalo 2010-07-01T12:50:56Z 2010-07-02T15:38:24Z <p>Well, in the absence of any answers, perhaps this might help somebody to get a proper solution.</p> <p>In order to show that there are infinitely many <em>composite</em> pairs of the form $n!\pm1$, it would suffice to prove that the expected number of <em>prime</em> numbers of the form $n!\pm1$ is relatively small, i.e. $$\limsup\limits_{N\to\infty}\frac{E|\{n=1,\dots,N|\ n!+1\ \mbox{or } n!-1\ \mbox{is prime}\}|}{N}=0.$$</p> <p>Now, there is <a href="http://www.utm.edu/staff/caldwell/preprints/primorials.pdf" rel="nofollow">a note</a> by Caldwell and Gallot (who were mentioned in Kevin Buzzard's comment avove) which contains a non-rigorous probabilistic argument yielding a heuristic estimate of the expectation.</p> <p>In short, they start with a rough assumption that $n!\pm1$ behaves like a random variable and use the Stirling formula $\log n!\sim n(\log n-1)$. The prime number theorem shows that the probability of a random number of the size $\sim n!\pm1$ being prime is $$P_n\sim\frac{1}{n(\log n-1)},\quad n\gg 1.$$ Then they take into account Wilson's theorem and some other obvious obstacles to $n!\pm1$ behaving randomly, and obtain just a slightly weaker estimate $$P_n\sim\left(1-\frac{1}{4\log 2n}\right)\frac{e^\gamma}{n}$$ where $γ$ is the Euler–Mascheroni constant. The latter estimate translates into the estimate of the expected number of factorial primes of each of the forms $n!\pm1$, $n\leq N$<br> $$E_N\sim e^\gamma \log N,\quad N\gg 1.$$</p> <p>Now, this is actually more than we need, and hopefully the probabilistic argument can be made rigorous to show that $E_N/N$ goes to $0$ as $N\to\infty$.</p> <p><strong>Edit added.</strong> </p> <blockquote> <p>Is it true that for every positive integer $B$ there is a positive integer $N$ such that $N$ is divisible by all primes up to $B$, and $N \pm 1$ are both composite?</p> </blockquote> <p>The modified question is easy. Take $N=(B!)^3$. </p> http://mathoverflow.net/questions/30101/composite-pairs-of-the-form-n-1-and-n1/37220#37220 Answer by Noah S for Composite pairs of the form n!-1 and n!+1 Noah S 2010-08-31T05:55:39Z 2010-08-31T05:55:39Z <p>As far as nonstandard models go: we can indeed get $\mathbb{Z}$-like intervals $I$ such that each $x\in I$ has a standard factor. The proof is via Compactness, and the Chinese Remainder Theorem:</p> <p>First, adjoin a constant symbol $c$ to our language. Let $p_i$ be the $i^{th}$ prime number, let $q_i=p_{2i}$, and let $r_i=p_{2i+1}$.</p> <p>Define numbers $a_i$, $b_i$ by recursion as follows:</p> <p>$a_0=0$, $a_{n+1}=\min\lbrace x: \forall k\in\mathbb{N}, j\le n(c\not=a_j+kq_j)\rbrace$</p> <p>$b_0=0$, $b_{n+1}=\min\lbrace x: \forall k\in\mathbb{N}, j\le n(c\not=b_j+kr_j)\rbrace$</p> <p>Now, for each $i\in\mathbb{N}$, let $\sigma_i$ express "$c$ is congruent to $-a_i$(mod$p_i$)", let $\tau_i$ express "$c$ is congruent to $b_i$(mod$p_i$)," and let $\Sigma=\lbrace \sigma_i: i\in\mathbb{N}\rbrace\cup\lbrace \tau_i: i\in\mathbb{N}\rbrace$. By the Chinese Remainder Theorem, every finite subset of $\Sigma$ is consistent with True Arithmetic $TA$, so by Compactness, $\Sigma$ itself is consistent with $TA$. So there is some nonstandard model of $TA$ in which $\Sigma$ holds; clearly, in such a model, every number in the $\mathbb{Z}$-like interval centered on $c$ has a standard factor.</p> <p>I have no idea whether $every$ nonstandard model has such an interval, however.</p> http://mathoverflow.net/questions/30101/composite-pairs-of-the-form-n-1-and-n1/37265#37265 Answer by Franz Lemmermeyer for Composite pairs of the form n!-1 and n!+1 Franz Lemmermeyer 2010-08-31T15:03:39Z 2010-08-31T15:03:39Z <p>Explicit constructions of infinitely many examples seem to be difficult. Looking at a table of factorizations of $N! \pm 1$ I noticed the following pattern (and now I see that this is essentially what Dror suggested in his comment):</p> <p>Assume that $q \equiv 3 \bmod 4$ and $p = \frac{q+3}2$ are prime numbers. Then for $n = p-2$, we have $p \mid n!-1$ and $q \mid n!+1$ if $h(-q) \equiv 1 \bmod 4$, where $h(m)$ denotes the class number of ${\mathbb Q}(\sqrt{m})$. Probabilistically, the class number of $h(-p)$ should be $\equiv 1 \bmod 4$ in half the cases. </p>