15
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ 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\ \ $ $\endgroup$ – Bill Dubuque Jan 4 '15 at 16:50
6
$\begingroup$

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

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – bertalanp99 Sep 9 '17 at 10:37
  • $\begingroup$ @bertalanp99 You're absolutely right! That's even more spoonfeedy! Mwahahaha! $\endgroup$ – The Short One Sep 11 '17 at 21:07
  • $\begingroup$ I think we should use $(n + 1)!$ because with $n!$ we would only get $n-1$ compound numbers. $\endgroup$ – bertalanp99 Sep 14 '17 at 21:31
  • $\begingroup$ @bertalanp99 Maybe you should post an answer, too. Feel free to downvote me as well, I wanna get my score back down to 666. $\endgroup$ – The Short One Sep 19 '17 at 21:22
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.