2
$\begingroup$

This is a question that came up while I was doing an exercise. I ended up with the number

$$ 200! + 1$$

and I want it to be composite but I don't know of any methods to check whether a number is prime or not.

Is there any general rule about $n+1$ or $n! + 1$ to determine if or when these are prime or composite?

The exercise I was doing when I ended up stuck at this question was this:

Show that there exists $n \in \mathbb N$ such that $n, n+1 \dots, n+200$ are all composite.

I am hoping for a solution not using calculators, software or the internet. I expect there to be a short and (computationally) simple answer. At least that's what I hope.

$\endgroup$
13
  • 1
    $\begingroup$ $n+1$: definitely not, since every integer is of this form. $\endgroup$
    – vadim123
    Oct 20, 2015 at 1:47
  • 1
    $\begingroup$ Wilson's theorem gives a useful result: if $n+1$ is prime then it divides $n!+1$. Unfortunately $201$ is not a prime so it does not apply here. $\endgroup$
    – Winther
    Oct 20, 2015 at 1:50
  • 2
    $\begingroup$ Wolfram was able to answer this, and gives $200!+1 = 1553\times 826069\times 353297821\times k$ where $k$ is a very large prime number that won't fit on this page. $\endgroup$
    – JMoravitz
    Oct 20, 2015 at 1:52
  • 2
    $\begingroup$ There is an ongoing project here that searches for primes on that form (known as factorial primes). $\endgroup$
    – Winther
    Oct 20, 2015 at 1:56
  • 1
    $\begingroup$ If you use $210!$ instead of $200!$ you can apply Wilson's theorem since $211$ is prime. $\endgroup$
    – Paul Hankin
    Oct 20, 2015 at 4:04

2 Answers 2

Reset to default
1
$\begingroup$

As to the original question, primes of the form $n!\pm 1$ are known as factorial primes and not all are known. It is in general a complicated question to determine if a number is prime or not, and only partial results are known. For example, if $n+1$ is prime then $n!+1$ is not.

As for the exercise which prompted this question, proving that there exists some $n$ such that $n,n+1,n+2,\dots,n+200$ are all composite consider the following:

Suppose we want to force each $n+i$ to be composite. If we want to force $2\mid n$ and $3\mid (n+1)$ and $5\mid (n+2)$, etc... that would correspond to the system of congruencies:

$\begin{cases} n\equiv 0\pmod{2}\\ n+1\equiv 0\pmod{3}\\ n+2\equiv 0\pmod{5}\\ \vdots\\ n+200\equiv 0\pmod{p_{201}}\end{cases}$

Consider then the Chinese Remainder Theorem.

The Chinese remainder theorem states that we can find such an $n$ that satisfies all of those congruencies since each of what we are modding out by are relatively prime to one another in every case.

Note: there is nothing intrinsically special about ordering these as being modulo $2$ followed by $3$ followed by $5$, etc... So long as we pick a list of length 200 where each of the entries on the list are coprime to one another, this will work.

Edit: Minor missing detail. It is possible that $n+i=p_i$ in one of those cases. To account for this possibility, technically chinese remainder will give us a solution to $n\equiv k\pmod{\prod p_i}$, so we can avoid this by instead of taking the smallest positive integer $n$ that works, by instead taking $n+\prod p_i$.

$\endgroup$
2
  • $\begingroup$ So the question isn't asking you for a specific $n$? The Chinese Remainder Theorem solves this, as we're only looking for the existence of such an $n$, just put the numbers you're adding by, on the other side, because there are infinitely many primes, which are definitely coprime to one another. $\endgroup$
    – Almentoe
    Oct 20, 2015 at 2:32
  • $\begingroup$ That is the way it is worded. In fact, the same proof can be modified to show the existence of arbitrarily long prime gaps. If you wanted to find an exact value for n, it could be done but would be incredibly tedious to do. $\endgroup$
    – JMoravitz
    Oct 20, 2015 at 2:41
0
$\begingroup$

As others have mentioned, it is not easy in general to check whether numbers of the form $n! + 1$ are prime. But as you may have noticed, the numbers $200! + 2$, $200! + 3, \dots, 200! + 200$ are all composite, as they are divisible by the numbers $2, 3, \dots, 200$ respectively. This gives only 199 consecutive composite numbers rather than the 201 required by your problem, but that's nothing that can't be fixed by increasing $n$ a little.

$\endgroup$
1
  • 2
    $\begingroup$ Or noting that $200! + 201$ and $200! + 202$ are composite since they're divisible by 3 and 2 respectively. $\endgroup$
    – Paul Hankin
    Oct 20, 2015 at 4:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .