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.

  • 0
    If someone have a better title for this, or can add tags, feel free in do it.2011-07-20
  • 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.$$

  • 1
    By the way, most of the credit here should go to OEIS: http://oeis.org/A1008582011-07-21
  • 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
    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?2011-07-20
  • 0
    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?2011-07-20
  • 0
    @Theo: I have heard the same story! I remember who told it to me, (a graduate student) but I don't remember a source...2011-07-20
  • 7
    @Theo: [Frank Nelson Cole](http://en.wikipedia.org/wiki/Frank_Nelson_Cole) in 1903 for $2^{67}-1$, which is a Mersenne number not a Fermat number.2011-07-20
  • 0
    @Henry: 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...

  • 1
    http://oeis.org/A0927912011-07-28
  • 0
    Thanks, I wonder if there are any more at all then!2011-07-29
  • 0
    @user826788: thanks a lot2011-09-25