Prove that $n! + k$ is a composite number

Solution 1:

For part a, note that for $ 1 < k \leq n$, we have that $k \mid n!$ since $k$ is in the product expansion of $n! = n(n-1)(n-2) \cdots (k)(k-1) \cdots 1$. Thus you can say $n! = c_1k$ for some integer $c_1$ and thus $n! + k = c_1k + k = k(c_1 + 1)$ which is divisible by $k$ and thus not prime.

For part b, you just need a $n > 100$ so that $1 < k \le 101$ will give you a hundred composite integers. For ex., let $n=105$. Then a hundred consecutive composite integers are:

$$ 105! + 2, 105!+3, 105!+4, \dots, 105! + 101 $$

namely all numbers of the from $105! + k$ for $1 < k \leq 105$.

You can extend this notion to any positive integer $\ell$. Say you want $\ell$ consecutive integers that are composite. Then choose $n$ s.t. $n > \ell$ and then your consecutive composite numbers will be of the form:

$$n! + k$$ for all $1 < k \leq \ell+1 \leq n$.

As for part c., Michael Hardy gave a very nice parallel as to why an unbounded increase in consecutive primes does not contradict that there are infinitely many of them.

Here is a further view. By the prime number theorem, we can say that the number of primes less than or equal to $x$, denoted $\pi(x)$ is given by:

$$ \pi(x) \sim \frac{x}{\ln x}. $$

and so we can very roughly claim that the number of primes in the interval $[x, x+l]$ for some fixed width $\ell$, is given by the function*:

$$ n(x) = \frac{x+\ell}{\ln (x + \ell)} - \frac{x}{\ln x} $$

*Note: it's not actually given by this function but it grows in this manner.

As you can see, this is a decreasing function. This is essentially saying, if you took a sliding window of fixed width $\ell$ and slide it up the number line, the number of primes that fall within that window would decrease as you slide the window higher. This very much matches the intuition of our method for finding $\ell$ consecutive numbers because if $\ell$ is to be large, then we have to start with a larger factorial (i.e. we need to start our window at larger values of $x$), so that there are no primes in that range and thus we can get $\ell$ consecutive composite numbers.

This last part is kind of tangential and not a rigorous proof (actually it is kind of erroneous reasoning) but is a sanity check to the fact that our methodology conforms to how primes are distributed.

Solution 2:

$$ 1\times2\times3\times4\times \cdots \cdots \times k \times \cdots\cdots\times (n-2)\times(n-1)\times n $$ The number above is divisible by $k$ since $k$ is in there, along the way from $1$ up to $n$. Hence when you add $k$ to it, getting $$ \Big(1\times2\times3\times4\times \cdots \cdots \times k \times \cdots\cdots\times (n-2)\times(n-1)\times n\Big) + k, $$ the result is still divisible by $k$, hence it is composite.