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

Recall that if $n$ is a positive integer, $n! = n(n-1)\cdots 3\cdot2\cdot1$.

a) Let $n$, $k$ be positive integers with $1< k \le n$. Prove that $n! + k$ is composite.

b) Using part a, find $100$ consecutive integers all of which are composite.

c) In part b you gave a sequence of $100$ consecutive integers all of which are composite. You should be able to use the same idea to find $\ell$ consecutive integers which are composite for any positive integer $\ell$. In other words, you can find sequences of any length which consist of consecutive integers and contain no primes. Does this contradict the fact that there are an infinite number of prime numbers?

• Hint $5! + 3$ is divisible by $3$.
– dxiv
Sep 29 '16 at 1:38
• Why would that last statement contradict the existence of infinitely many primes? There are infinitely many squares, and yet the set of sizes of gaps between consecutive squares is unbounded. $\qquad$ Sep 29 '16 at 1:42
• – user354674
Sep 29 '16 at 4:55
• There are infinitely many prime numbers and infinitely many composite numbers. No contradiction between these two facts. Sep 29 '16 at 6:12

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

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.