8
$\begingroup$

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.

  • 1
    I think *composite* may be more conventional here than *compound*2011-07-20

5 Answers 5

15

This is false.

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

  • 4
    @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.2011-07-21
6

This is a comment about your second question.

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.

  • 0
    @Henr$y$: Thanks a lot for that!2011-07-20
3

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

3

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

  • 0
    Yes, it is true. Thank you . Now this make me think that my question is too simple, maybe all this is not worth.2011-07-24
1

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

  • 0
    @user826788: thanks a lot2011-09-25