Consider the following problem:

Prove or disprove that if $n\in \mathbb{N}$, then $n$ is prime iff $$(n-1)!+n$$ is prime.

If $n$ is composite and greater than $1$, then $n$ have a divisor less than $n-1$, therefore $(n-1)!$ and $n$ have a common factor. Thus "$\Leftarrow$" is true. To proof the other direction we can consider the more general problem:

Let $n\in\mathbb{N}$. Consider the set $$C(n)=\{m\in\mathbb{N}:n+m\text{ is composite}\}.$$ How we can characterize the elements of $C(n)$?

The ideal answer would be describe all elements in $C(n)$ in terms of only $n$. But, is that possible? I have asked this question to my professors and they simply smile (is not fun for me, I mean, is a serious question, or not?) and then say $$C(n)=\{jk-n:j,k\in\mathbb{N}\}.$$ But, this is obvious and don't help me. I tell you all this history because I want to know what do you think about it, and if exist literature that mention something like this problem.

As a first approximation to solve this, we can start by defining for $n,p\in\mathbb{N}$: $$A(n,p)= \{ m\in\mathbb{N}:n+m\equiv 0\pmod{p} \}.$$ After of some observations we can prove that $$A(n,p)=\{(\lceil n/p \rceil + k)p - n:k\in \mathbb{N}\}$$ and then $A(n,p)$ is the range of a function of the form $f_{n,p}:\mathbb{N}\to \mathbb{N}$. From this $$C(n)=\bigcup_{p=2}^\infty A(n,p),$$ But this still far from a characterization in terms of $n$. What do you think that is the better that we can do or the best we can hope?

Edit: I really want to know what do you think about the problem of characterize the elements of $C(n)$ or $\mathbb{N}\setminus C(n)$. Any opinions, suggestions, corrections, comments and/or references are greatly appreciated.

-
If someone have a better title for this, or can add tags, feel free in do it. – leo Jul 20 '11 at 22:43
Thank you @Theo. – leo Jul 20 '11 at 23:02
I think composite may be more conventional here than compound – Henry Jul 20 '11 at 23:25

This is false.

$$29 | 479001613 = (13 - 1)! + 13.$$

-
Thank you @DJC. – leo Jul 20 '11 at 22:58
By the way, most of the credit here should go to OEIS: oeis.org/A100858 – JavaMan Jul 21 '11 at 1:29
@leo: One other comment about this problem. If the statement in the first sentence of you post were true, then we could construct arbitrarily large prime numbers. Since it isn't the case that we can construct such primes, this gives us more evidence of why such a statement isn't likely to hold. – JavaMan Jul 21 '11 at 2:36

Since $$C(n)=\mathbb{N} \backslash \{ m\in\mathbb{N}: \ m+n\ \text{ is prime} \}$$

being able to say nice things about $C(n)$ for every $n$ implies we can say nice things about the set of primes shifted by $n$. However, the primes are very complicated creatures which have been studied for thousands of years, and it is very hard to write down their explicit structure.

-
Eric: somehow DJC's answer reminded me of this story about a guy giving a talk that consisted only of a long division (maybe the factorization of the 6th or 7th Fermat "prime"?). I have no idea where I picked this up and how I could find out about it. Do you happen to know where this might come from? – t.b. Jul 20 '11 at 23:06
Characterize the elements of $C(n)$ is equivalent to characterize the elements of $\mathbb{N}\setminus C(n)$. And what about this? Exist references to this explicit problem? – leo Jul 20 '11 at 23:07
@Theo: I have heard the same story! I remember who told it to me, (a graduate student) but I don't remember a source... – Eric Naslund Jul 20 '11 at 23:19
@Theo: Frank Nelson Cole in 1903 for $2^{67}-1$, which is a Mersenne number not a Fermat number. – Henry Jul 20 '11 at 23:30
@Henry: Thanks a lot for that! – t.b. Jul 20 '11 at 23:32

Note that the smallest counterexample is easily verified by hand in a minute or so:

$\rm\ mod\ 29:\ \ 12\:!\ =\ (4\cdot 7)\ (3\cdot 10)\ (5\cdot 6)\ (8\cdot 11)\ (2\cdot 12\cdot 9)\ \equiv\: -1\cdot 1^3\cdot 8\cdot (3\cdot 9)\ \equiv\ 16$

Thus $\rm\ 12!+13\ \equiv\ 16+13\ \equiv\ 0\ \ (mod\ 29)$

-

One reason your professors might have smiled at you is that

$$C(n) = C(0) - n,$$

where $C(0) = \{m \in \mathbb N: m \text{ is composite} \}$. So characterizing $C(n)$ reduces to characterizing $C(0)$, which in turn reduces to characterizing the set of primes $\mathbb N \setminus C(0)$.

(Well, okay, technically $C(n) = (C(0) - n) \cap \mathbb N$ as you've defined it, but cutting off the negative part of the set doesn't make any fundamental difference.)

-
Yes, it is true. Thank you . Now this make me think that my question is too simple, maybe all this is not worth. – leo Jul 24 '11 at 18:58

I've verified with Python (using Miller-Rabin) that the only numbers it works for less than 300 are 1, 2, 3, 5, 7, 11 and 53. That's it.

So unfortunately, it rarely works at all but this is true of almost every formula designed to generate large primes. Primes are possibly the most mysterious and unpredictable objects in mathematics. You probably know of Fermat and Mersenne numbers which are ideal to discover really large primes BUT not because they're dense in primes (which they aren't in the long run) but because they're in a format suitable for efficient computer algorithms.

Long ago, I had a short-lived theory that $|p_{n+1}^2-p_n!?|$ was always prime, where $p_n$ is the n-th prime and $p_n!?$ is the product of the first n primes... It's easy to prove it works if it's positive (without the absolute value) but that doesn't last long :(

Don't give up though, try to see if the factors have a pattern and then prove it. Cut things down (the same way you showed that n has to be prime) if that makes sense. As for C(n), it's as hard as understanding the primes themselves like @Ilmari and @Eric have said. You might be interested in looking at primes in other rings or in certain modulo classes...

-
oeis.org/A092791 – JavaMan Jul 28 '11 at 16:00
Thanks, I wonder if there are any more at all then! – user826788 Jul 29 '11 at 7:27
@user826788: thanks a lot – leo Sep 25 '11 at 3:10