Exercise 1.3.28 ($ \sum_{k=1}^n k$ divides $\prod_{k=1}^n k$ iff $n+1$ is composite)

Proof. Let $S$ be the sum of positive integers not exceeding $n$, and $P$ the product of the positive integers not exceeding $n$, where $n>1$. Then

• Suppose that $S\mid P$, so that

  $$\frac{n(n+1)}{2}\mid n!.$$
  • If $n>1$ is odd, then $n+1$ is even, where $n+1\ne 2$, thus $n+1$ is composite.

  • If $n$ is even, then

    $$\frac{n}{2}(n+1)\mid n(n-1)!,$$

    thus

    $$n+1\mid 2(n-1)!.$$

    Here $(n+1)\wedge 2=1$, thus

    $$n+1\mid (n-1)!.$$

    If $n+1$ was a prime, then $n+1\mid k$, for some integer $k$ such that $1\le k<n$, and so $n+1\le k<n$. This is absurd, therefore $n+1>1$ is composite.

• Conversely, suppose that $n+1$ is composite. Therefore $n\ne 2$. If $n=3$, then $\frac{3(3+1)}{2}=6\mid 3!$, so we may suppose $n>3$.

  By problem 27, where $n$ is replaced by $n+1$, $n+1\mid n!$, since $n>3$.

  If $n$ is even, $(n∕2)!\mid n!$ and $n+1\mid n!$, where $(n∕2)\wedge (n+1)=1$, thus $(n∕2)(n+1)\mid n!$.

  If $n$ is odd, $(n+1)∕2\mid n!$ and $n\mid n!$, where $[(n+1)∕2]\wedge n=1$, thus $((n+1)∕2)n\mid n!$.

  In both cases, $\frac{n(n+1)}{2}\mid n!$, so $S\mid T$.

The sum $S$ of positive integers not exceeding $n$ divides the product $P$ of the positive integers not exceeding $n$ if and only if $n+1$ is composite. □