Question

i need a very detailed proof

(Show your work!)

Let n > 1. Prove: The sum of the positive integers less than or equal to n is a divisor of the product of the positive integers less than or equal to n if and only if n + 1 is composite.

  

Answer 1

The sum of the positive integers less than or equal to n is,

S = 1+2+3+4+...+n = n(n+1)/2

& The product of the positive integers less than or equal to n is, P = 1.2.3. ... .n = n!

We need to show, S divides P if and only if n+1 is composite.

Suppose, n+1 is composite.

Then, P/S = n!/{n(n+1)/2} = 2.(n-1)!/(n+1)

Now, if n+1 is composite, then there exists positive integers a & b such that,

n+1 = a.b & 1 < a < n & 1 < b < n & gcd(a,b) = 1

Since, 1<a<n & 1<b<n, so, a | (n-1)! & b | (n-1)!

Also, gcd(a,b) = 1 implies, a.b | (n-1)!

i.e. (n+1) | (n-1)!

So, (n+1) | 2.(n-1)!

So, 2.(n-1)!/(n+1) is an integer.

So, P/S is an integer

So, S | P

Now, for the converse, suppose, S | P

We need to show, n+1 is composite.

On the contrary, assume that, n+1 is not composite, i.e. n+1 is prime

Then, by, Wilson's theorem, (n+1) divides (n+1-1)! + 1

i.e. (n+1) divides, n! + 1

Again, by, S | P, we have, (n+1) divides, 2.(n-1)!

So, (n+1) also divides, 2.n.(n-1)!

i.e. (n+1) divides, 2.n!

Since, n>1 so, n+1>2 & n+1 is a prime

So, n+1 is a prime greater than 2

So, gcd(n+1, 2) = 1

So, (n+1) | 2.n! implies that, (n+1) | n! [By, Euclid's Lemma, that, if c | a.b & gcd(a,c) = 1, then, c | b]

So, we have, (n+1) | n!

Again, we had, (n+1) | (n! + 1)

So, (n+1) | {n! + 1 - n!}

So, (n+1) | 1, so, n+1 = 1, so, n = 0, which is a contradiction.

Hence, our initial assumption was wrong that, n+1 is prime.

So, n+1 is composite.

Hence, proved both side implications