Prove that an odd integer $n>1$ is prime if and only if it is not expressible as a sum of three or more consecutive integers.
I can see how this works with various examples of the sum of three or more consecutive integers being prime, but I can't seem to prove it for all odd integers $n>1$. Any help would be great.
Best Answer
First of all, you can assume you're adding only positive numbers; otherwise the question isn't correct as written.
Note that the sum of the numbers from $1$ to $n$ is ${\displaystyle {n^2 + n \over 2}}$. So the sum of the numbers from $m+1$ to $n$ is ${\displaystyle {n^2 + n \over 2} - {m^2 + m \over 2} = {n^2 - m^2 + n - m \over 2} = {(n - m)(n + m + 1) \over 2}}$. You want to know which odd numbers $k$ can be written in this form for $n - m \geq 3$.
If $k$ were a prime $p$ that could be expressed this way, then you'd have $(n- m )(n+m+1) = 2p$. But $n - m \geq 3$, and $n + m + 1$ would only be bigger than that. Since $2p$ has only the factors $2$ and $p$, that can't happen.
So suppose $k$ is an odd non-prime, which you can write as $k_1k_2$ where $k_1 \geq k_2$ are odd numbers that are at least $3$. You now want to solve $(n-m)(n+m+1) = 2k_1k_2$. It's natural to set $n - m = k_2$ (the smaller factor), and $2k_1 = n + m + 1$, the larger factor. Solving for $n$ and $m$ one gets ${\displaystyle n = {2k_1 + k_2 - 1 \over 2}}$ and ${\displaystyle m = {2k_1 - k_2 - 1 \over 2}}$. Since $k_1$ and $k_2$ are odd these are both integers. And since $k_1 \geq k_2$, the numbers $m$ and $n$ are nonnegative.