Exercise 1.3.41* (Primes and sum of consecutive integers.)

Proof. Let $n>1$ be any odd integer.

• We prove first that if $n$ is a sum of three or more consecutive positive integers, then $n$ is not a prime.

  By Exercise 40, if $n$ is sum of $k+1$ consecutive positives, with $k\ge 2$, then

  $$n=\frac{(k+1)(2m+k)}{2},m>0,k\ge 2.$$

  $\text{−}$

  If $k$ is odd, $n=\frac{k+1}{2}(2m+k)$, where $\frac{k+1}{2}$ and $2m+k$ are integers.

  $\text{−}$

  If $k$ is even, $n=(k+1)\frac{2m+k}{2}$, where $k+1$ and $\frac{2m+k}{2}$ are integers.

  Since $m\ge 1$ and $k\ge 2$, $\frac{k+1}{2}\ge \frac{3}{2}>1$, and $\frac{2m+k}{2}\ge \frac{3}{2}>1$. A fortiori $2m+k>1$ and $k+1>1$. Hence in both cases $n$ is composite.

• Conversely, we show that if $n>1$ is odd and composite, then $n$ is a sum of three or more consecutive positive integers.

  Since $n$ is odd and composite, $n$ is a product of at least two odd primes:

  $$n=p_1{p}_2\cdots p_l,p_1\le p_2\le \cdots \le p_{l}l\ge 2,$$

  where $p_1,p_2,\dots ,p_l$ are odd primes.

  Write $p=p_1$ the least prime divisor of $n$, and define

  $$k=p-1,m=\frac{n}{p}-\frac{p-1}{2}.$$

  Then

  $$\frac{(k+1)(2m+k)}{2}=p\left(m+\frac{p-1}{2}\right)=p\frac{n}{p}=n,$$

  where $k,m$ are integers, and $k\ge 2$ because $p\ge 3$ is an odd prime.

  It remains to verify that $m>0$.

  $$\begin{array}{llll}\hfill m>0& ⟺\frac{n}{p}>\frac{p-1}{2}& \hfill & \\ \hfill & ⟺p-1<2\frac{n}{p}& \hfill & \\ \hfill & ⟺p\le 2\frac{n}{p}(\text{because }p\text{ and }2\frac{n}{p}\text{ are integers})& \hfill & \\ \hfill & ⟺p^2\le 2n.& \hfill & \end{array}$$

  This last inequality is true, because $n$ is composite, so $l\ge 2$ and by (1)

  $$n=p_1{p}_2\cdots p_l\ge p_1{p}_2\ge p_1^2=p^2,$$

  so $p^2\le n$, a fortiori $p^2\le 2n$. This proves $m>0$. Therefore

  $$n=\frac{(k+1)(2m+k)}{2},m>0,k\ge 2,$$

  thus $n$ is a sum of three or more consecutive positive integers.

Taking the negations, these two parts show that an odd integer $n>1$ is a prime if and only if it is not expressible as a sum of three or more consecutive positive integers. □