Track / Stage 4 / 135 of 340 #875 of 2444

Problem 875

AMC 12 late, AIME early

Number theory Difficulty 4.7 Prove it NMO Selection Tests for JBMO · Romania

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$ .

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

The statement of the problem is equivalent to saying that an integer $n \ge 5$ is composite if and only if there exists a representation of $n$ as the sum of four positive integers such that $ab = cd$ .

( $\Leftrightarrow$ ) If $ab = cd$ and $n = a+b+c+d$ , then
$an = a^2 + ab + ac + ad = a^2 + cd + ac + ad = (a+c)(a+d), (*)$
hence $n \mid (a+c)(a+d)$ .

( $\Rightarrow$ ) If $n = pq$ , with $p, q \ge 2$ , is a composite number, we can choose $a = 1$ , $b = (p-1)(q-1)$ , $c = p-1$ , $d = q-1$ . This choice can easily be guessed by writing $(*)$ with $a = 1$ .

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.