7
$\begingroup$

There is a famous theorem in number theory called Wilson's Theorem.

Statement: $n$ satisfies, $(n-1)! + 1 = 0\pmod n$ if and only if $n$ is prime.

Another way of looking at the statement is that, $\dfrac{(n-1)! + 1}{n}$ is an integer only if $n$ is prime.

I have noticed a pattern in these integers. They always come out to be prime. I have made a code, to test primes upto a large number, and all of the integers that have come from the fraction, is found to be prime. If the aforementioned statement always holds true for all primes, then it would behave as a prime generator. I haven't found any useful information currently existing on the internet.

Hence, I am looking for a mathematical proof for the following:

Let $f:\mathbb{N}\to\mathbb{N}$ be defined as, $$f(n) = \frac{(n-1)! + 1}{n}$$for all $n\in\mathbb{N}$.

Prove that: $$f(n)\in \mathbb{P};\ \ \forall n \in\mathbb{P}$$ Where $\mathbb{P}$ is the set of Primes.

Now, I do know that for $n = {2,3},\ f(n) = 1$. This should be ignored as sometimes, $1$ trivially shows up while working with primes.

$\endgroup$
  • 3
    $\begingroup$ $f(13) = 13 \cdot 2834329$, $f(17) = 61 \cdot 137 \cdot 139 \cdot 1059511$. $f(p)$ is prime (or probably prime according to BPSW) for $p = 5, 7, 11, 29, 773, 1321$, and no other "small" primes. $\endgroup$ – Daniel Fischer Jul 30 '17 at 14:11
  • 2
    $\begingroup$ @HyperBean, $\frac{(n-1)!+1}n\approx (n-2)!$, so these numbers rapidly outrange the computational capabilities of elementary algorithms in most programming languages. I wouldn't be surprised if your result depended on this. $\endgroup$ – user228113 Jul 30 '17 at 14:17
  • 1
    $\begingroup$ $f(n)$ is called the "Wilson quotient" (in analogy with the Fermat quotient). Search on that term to learn more about the long history of this and related topics. $\endgroup$ – Bill Dubuque Jul 30 '17 at 14:24
  • 1
    $\begingroup$ I'm sorry, I have figured out a crucial error I'm my code. I apologize for this and I thank everyone for their support in their answers. $\endgroup$ – HyperBean Jul 30 '17 at 14:27
6
$\begingroup$

It is not always prime: $ f(13) = 13 \times 2834329 $. For the primes $ 2 \leq p \leq 997 $, the only time $ f(p) $ is (probably) prime is for $ p = 5, 7, 11, 29, 773 $.

$\endgroup$
3
$\begingroup$

That's false. First counterexample $13$.

$$\frac{(13-1)! +1}{13} = 36846277 = 13 \times 2834329$$

And if you do not like that it is $13$ that shows up again take $17$.

$$\frac{(17-1)! +1}{17} = 1230752346353 = 61\times 137\times 139 \times 1059511$$

Or also $19$ and $23$. Then for $29$ it is prime again.

A reason why it is plausible that it is true for small $n$ frequently is that $(n-1)!+1$ cannot be divisible by any primes less than $n$. But otherwise there is not much reason for this to be prime, though it should still be prime a bit more frequently than a typical number of that size.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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