Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.