Checking whether a number is prime or composite

Question

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.

Answer 1

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

Answer 2

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.