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

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.

-
Hint: write $(a+1) + (a+2) + ... + (a+k) = k a + (1+2+...+k)$. Can you evaluate the sum? Why is the resulting number not prime (what divides it?), and why can any odd composite integer $n>1$ be written in this form (what should you choose for $k$?) –  mjqxxxx Feb 9 '11 at 1:55
A minor technicality: $3=0+1+2$ (and of course only positive integers are considered). –  Jonas Meyer Feb 9 '11 at 2:16

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.

-
To elaborate a little, $m\cdot n = n + n + \cdots +n = \cdots + (n-1) + n + (n+1) + \cdots$.
Conversely, $(n-k) + \cdots + (n+k) = \cdots$.