# Proof of non-prime integers.

$a_1, a_2$ and $a_3$ are distinct positive integers, such that

$a_1$ is a divisor of $a_2 + a_3 + a_2a_3$

$a_2$ is a divisor of $a_3 + a_1 + a_3a_1$

$a_3$ is a divisor of $a_1 + a_2 + a_1a_2.$

Prove that $a_1, a_2$ and $a_3$ cannot all be prime.

-

Assume that they are all primes.

The first equation gives $$(a_2 + 1)(a_3+1) \equiv 1 \mod{a_1}$$ so $(a_1+1)(a_2+1)(a_3+1) \equiv 1 \mod{a_1}$. Similarly, $(a_1+1)(a_2+1)(a_3+1) \equiv 1 \mod{a_2,a_3}$. If $a_1,a_2,a_3$ are distinct primes, this implies that $$(a_1+1)(a_2+1)(a_3+1) \equiv 1 \mod{a_1a_2a_3}$$ i.e. $a_1a_2 + a_2a_3 + a_3a_1 + a_1 + a_2 + a_3$ is divisible by $a_1a_2a_3$. This in particular means that $a_1a_2 + a_2a_3 + a_3a_1 + a_1 + a_2 + a_3 \ge a_1a_2a_3$. We will show that this is very unlikely except for some small $a_1,a_2,a_3$.

Without loss of generality assume that $a_1 > a_2 > a_3$.

Case (a): $a_3 \ge 3$. Then $a_2$ is at least 5 and $a_1$ is at least 7. Consider

$$(a_1 - 5)(a_2 - 3)(a_3 - 2) \ge 0$$

So $a_1a_2a_3 \ge 5a_2a_3 + 3a_1a_3 + 2a_1a_2 - 6a_1 - 10a_2 - 15a_3 + 30$. Now,

$$RHS > a_1a_2 + a_2a_3 + a_3a_1 + a_1 + a_2 + a_3 \\ \Leftrightarrow a_1a_2 + 2a_1a_3 + 4a_2a_3 + 30 > 7a_1 + 11a_2 + 16a_3 \\ \Leftrightarrow a_1(a_2 + 2a_3 - 7) + (2a_2 - 8)(2a_3 - 6) + a_2 - 18 > 0$$ But the first term is at least $7 ( 5 + 6 - 7) = 28$, so the last inequality is true, i.e. $a_1a_2a_3 > a_1a_2 + a_2a_3 + a_3a_1 + a_1 + a_2 + a_3$, which means that $a_1,a_2,a_3$ can't be all primes.

Case (b): $a_3 = 2$. Then $2 \mid a_1a_2 + a_1 + a_2$. But if $a_1,a_2$ are primes larger than 2, they are odd, making this impossible.

-
I prefer case b for it's simplicity, but either works. –  Neil Dec 13 '12 at 11:29
@Neil: It's not about either working; both cases need to be covered. –  joriki Dec 13 '12 at 12:57