Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

It's well known that the numbers of the form $n!\pm1$ are not always prime. Indeed, Wilson's Theorem guarantees that $(p-2)!-1$ and $(p-1)!+1$ are composite for every prime number $p > 5$.

Is there a proof, preferably an elementary proof, that there are infinitely many composite pairs of the form $n!\pm1$?

The motivation for this question comes from my answer to this recent question. 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.

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.

share|improve this question
9  
I don't know of an elementary proof, but in practice it's very rare that either of $n!\pm1$ are prime, so the result is surely true. For example, both $n!+1$ and $n!-1$ are composite for all $4000\leq n\leq 6000$. Caldwell and Gallot found that $6380!+1$ and $6917!-1$ were prime, but it gets harder and harder to find examples up there. NB I discovered this by computing the first few n for which $n!+1$ was prime and looking it up in Sloane and chasing up the references. –  Kevin Buzzard Jun 30 '10 at 19:59
1  
If for a prime $q$, $2q−3$ is also prime, then $n=q-2$ makes for a composite pair. Simply put, this doesn't help –  Dror Speiser Jun 30 '10 at 21:07
1  
It seems like "elementary proof" has a specific technical meaning here; what is it? Also, just to be clear: we do not as yet know of any proof, right? –  Pete L. Clark Jun 30 '10 at 22:19
    
@Pete: For the intended application to work, the proof has to be formalizable in PA. I'm not that picky, any proof will do for now. –  François G. Dorais Jun 30 '10 at 22:25
2  
@Dror: I don't think your assertion is correct. Try $q=13$ for a counterexample. Let me conjecture the slip you made: if $p$ (your $2q-3$) is a prime which is 3 mod 4 and $n=(p-1)/2$ then $(n!)^2$ is 1 mod $p$ but the problem is that $n!$ could be either $+1$ or $-1$ mod $p$. –  Kevin Buzzard Jun 30 '10 at 23:03

3 Answers 3

Well, in the absence of any answers, perhaps this might help somebody to get a proper solution.

In order to show that there are infinitely many composite pairs of the form $n!\pm1$, it would suffice to prove that the expected number of prime 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.$$

Now, there is a note 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.

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$
$$E_N\sim e^\gamma \log N,\quad N\gg 1.$$

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

Edit added.

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?

The modified question is easy. Take $N=(B!)^3$.

share|improve this answer
    
Andrey, sorry for redacting the modified question. Thank you for pointing out the easy answer. –  François G. Dorais Jul 2 '10 at 15:43
3  
Hakuna matata. –  Andrey Rekalo Jul 2 '10 at 15:49

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

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.

share|improve this answer
    
Should probably mention in the final statement "for $p\equiv 3\mod 4$". –  Dror Speiser Aug 31 '10 at 16:53

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:

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}$.

Define numbers $a_i$, $b_i$ by recursion as follows:

$a_0=0$, $a_{n+1}=\min\lbrace x: \forall k\in\mathbb{N}, j\le n(c\not=a_j+kq_j)\rbrace$

$b_0=0$, $b_{n+1}=\min\lbrace x: \forall k\in\mathbb{N}, j\le n(c\not=b_j+kr_j)\rbrace$

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.

I have no idea whether $every$ nonstandard model has such an interval, however.

share|improve this answer
    
Since CRT is a theorem of PA, couldn't this construction be carried out up to some nonstandard N to get the required Z-interval? –  François G. Dorais Aug 31 '10 at 14:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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