Let $n \ge 5$ be an integer. Show that $n$ is prime if and only if $n_{i} n_{j} \neq n_{p} n_{q}$ for every partition of $n$ into $4$ integers, $n=n_{1}+n_{2}+n_{3}+n_{4}$, and for each permutation $(i, j, p, q)$ of $(1, 2, 3, 4)$.
Problem
Source:
Tags: LaTeX
Wolstenholme
16.06.2013 08:09
Actually the problem statement is false since it says "partition into integers" and we can just take n = n+0+0+0 so we proceed under the assumption that it means "positive integers." First, I shall show the "if" direction. Consider all composite positive integers n. First of all, if n is even, the result is trivial since we can take n= 1 + 1 + (n/2 - 1) + (n/2 - 1). Now, assume n is odd. If we prove the result for n = pq where p and q are two not necessarily distinct odd primes then we clearly have the result for all odd composite n because if n = pqA for some positive integer A, then we can take the sum for n = pq and multiply all four summands by A. Now, note that n = pq = (p-1)/2 + (p+1)/2 + ((q-1)/2 * (p-1)) + ((q-1)/2 * (p+1)) and clearly this sum satisfies the conditions. Therefore, if n is composite, such a sum exists. Now, we prove that if n is prime, such a sum does not exist. Let n = a + b + c + (bc)/a where (bc)/a => c => b => a => 1 (these are not arrows but "equal to or greater than" signs). Clearly a divides either b or c. But then n = (b+a)(c+a)/a so it is clear that this sum is composite, contradicting the fact that n is prime. So, the (very interesting) statement is correct. As a side note, I do not know Latex and if anyone could rewrite my work nicely that would be highly appreciated.
ZetaX
27.04.2014 12:15
Also, the part about the permutation is unnecessary.