# How do I prove that for every positive integer $n$, there exist $n$ consecutive positive integers, each of which is composite?

I need help proving that for every positive integer $n$, there exist $n$ consecutive positive integers, each of which is composite. The hint that came with the problem is: Consider the numbers $2+(n+1)!,3+(n+1)!,...,n+(n+1)!,n+1+(n+1)!$.

I honestly have no idea how to begin here. I am specifically confused about what it means when it says "there exist $n$ consecutive positive integers". Does this mean that if $n = 5$, for example, then somewhere in the positive integers there are 5 consecutive composite integers, and that we want to prove that? I get that composite means that they are not prime, so they have more factors than 1 and themselves.

Any help would be greatly appreciated.

Thank you!

• Hint $\,\ 2\mid m,\,3\mid m,\ldots,k\mid m\,\Rightarrow\, 2\mid m\!+\!2,\,3\mid m\!+\!3,\ldots,k\mid m\!+\!k\ \$ – Bill Dubuque Jan 4 '15 at 16:50

The numbers you are given are consecutive, right? Are they composite? Hint: For the term $i + (n+1)!$, try to factor out $i$...

To expand on the other solution already given,

Proof Assume $m$ and $n$ exists in the positive integers and that $m$ is less than $n$. If $m$ is less than $n$ then $$n!=1*2*3*\dotsb*m*\dotsb*n$$

which is to say that $m$ is a factor of $n!$. So \begin{align} m+n! &= m+(1*2*\dotsb*m*\dotsb*n) \\ &= m[(1*2*\dotsb*n)/m + 1] \end{align} Remember that $m$ is a factor of $n!$ and so $n!/m$ is still an integer. So since $m$ is an integer that is bounded between $1$ and $n$, it stands that whatever number you pick up to $n$ can divide $m+n!$ making it composite till the $n$th integer, but $n!$ has that $n$th integer in it so the $n$th integer is also composite which means that you can pick any integer between $1$ and $n$ inclusively and it will be composite.

This is called spoonfeeding, and human students are notorious for needing it.

Does this mean that if $n = 5$, for example, then somewhere in the positive integers there are 5 consecutive composite integers, and that we want to prove that?

Yes, that's exactly what that means. For example, $24, 25, 26, 27, 28$ are five consecutive composite integers. But $29$ is prime, so if you want a run of six consecutive composite integers, you have to go up a little further to find $90, 91, 92, 93, 94, 95, 96$. Actually, that's seven consecutive composites.

Of course it's inefficient to run through the integers in the hopes of finding a run of composite numbers of the desired length. If only there was some formula that guaranteed us a run of at least $n$ consecutive composites, but unfortunately there isn't. What woe, to be in such a hopeless situation!

Oh, wait a minute, what is this?

Consider the numbers $$2 + (n + 1)!, 3 + (n + 1)!, \ldots, n + (n + 1)!, n + 1 + (n + 1)!$$

We know that $n!$ is even for $n > 1$, which then means that $2 + (n + 1)!$ must also be even. And we also know that $n!$ is divisible by $3$ for $n > 2$, so $3 + (n + 1)!$ must also be divisible by $3$. And we also know that $n!$ is divisible by $4$ for $n > 3$... see where I'm going with this?

• Why do we need $(n+1)!$ and not just $n!$? We know that $n!$ is even for $n>1$, which means that $2+n!$ is also even. Then, $n!$ is divisible by $3$ for $n>2$, so $3+n!$ is also divisible by $3$. And so and so on. Is this incorrect? – bertalanp99 Sep 9 '17 at 10:37
• @bertalanp99 You're absolutely right! That's even more spoonfeedy! Mwahahaha! – The Short One Sep 11 '17 at 21:07
• I think we should use $(n + 1)!$ because with $n!$ we would only get $n-1$ compound numbers. – bertalanp99 Sep 14 '17 at 21:31
• @bertalanp99 Maybe you should post an answer, too. Feel free to downvote me as well, I wanna get my score back down to 666. – The Short One Sep 19 '17 at 21:22

Yes, if $n = 5$ then you want to prove there is a run somewhere of at least 5 consecutive composite integers (though if the run is longer that's fine).

Review the definition of factorial: $n! = 1 \times 2 \times 3 \times \ldots \times (n - 1) \times n$. So this means that $n!$ is divisible by 2, by 3, and by each number up to $n$, and also by some other numbers we don't need to worry about here. And $(n + 1)!$ is divisible by every number from 2 to $n + 1$.

In the example of $n = 5$, we look at $6!$. Now, $6! + 1$ may or may not be prime (that's easy enough to test for such a small number but not a pressing concern here). But certainly $6! + 2$ is even, $6! + 3$ is divisible by 3, $6! + 4$ is divisible by 2 and 4, $6! + 5$ is divisible by 5 and $6! + 6$ is divisible by 2, 3 and 6. $6! + 7$ may or may not be prime but you have your run of 5 consecutive composites already.

In general, if $\gcd(n, m) > 1$ then $n! + m$ is definitely composite. From the definition of the factorial it follows that $n!$ shares a prime factor with each $m$ in the range $1 < m \leq n$, ensuring a run of composites from $n! + 2$ to $n! + n$.

proof: Let n be any natural number and consider the numbers 2 + (n + 1)!, 3 + (n + 1)!, 4 + (n + 1)!, ....., n + (n + 1)!, (n + 1) + (n + 1)!. observe that 2 divides the number 2 + (n + 1)!, 3 divives the number 3 + (n + 1)! and n divides the n + (n + 1)! likewise (n + 1) divides (n + 1)!. In short i divides i + (n + 1)! where i is an element of the set. {2, 3, 4, ..., n, n + 1} the reason been you can always factor out i. Likewise the numbers 2 + (n + 1)!, 3 + (n + 1)!, 4 + (n + 1)!, ....., n + (n + 1)!, (n + 1) + (n + 1)! are all consecutive and their count is n. QED