Let $n \ge 5$ be an integer. Prove that $n$ is prime if and only if for any representation of $n$ as a sum of four positive integers $n = a + b + c + d$, it is true that $ab \ne cd$.
Problem
Source: 2014 Romania JBMO TST 4.3
Tags: primes, Sum, combinatorics, number theory
26.02.2021 10:05
We treat two cases, each proving one direction. Assume first that $n$ is composite. We want to prove that $n$ can be written as the sum of four positive integers such that $ab=cd$. Since $n$ is a composite, $n$ can be written as $n=xy$ with where $x, y\geq 2$ are positive integers. Pick $a=(x-1)(y-1), b=1, c=x-1, d=y-1$ and easily check that these values indeed works. We now treat the case when $n$ is a prime. Assume for contradiction that there are four numbers $a, b, c, d$ such that $ab=cd$ and $n=a+b+c+d$. Then, by the Four Numbers Lemma we can write $a=pq, b=rs, c=ps, d=qr$ for some $p, q, r, s\in\mathbb{N^{*}}$. But then $n=(p+r)(q+s)$ which is clearly not a prime, finishing our proof.
08.10.2023 14:42
If $n = xy$, $x,y \geq 2$, is composite, then $a=(x-1)(y-1)$, $b=1$, $c=x-1$, $d=y-1$ works. Suppose $n$ is prime. If $ab=cd$ and $n=a+b+c+d$, then $n = a+b+c+ \frac{ab}{c} = \frac{c^2+ac+bc+ab}{c}$, thus $cn = (c+a)(c+b)$. Since $n$ is prime, it divides at least one of $c+a$ and $c+b$; if without loss of generality this is $c+a$, then $\frac{c+a}{n} = \frac{c}{c+b} < 1$ is a positive integer, contradiction.