Olympiad Maths Prep

Track / Stage 5 / 179 of 400 #779 of 2000

Problem 779

AIME late
Number theory Difficulty 5.4 Find the answer

9.7. Find all triples of prime numbers p,q,rp, q, r such that the fourth power of any of them, decreased by 1, is divisible by the product of the other two.

(V. Senderov)

Official solution

# Answer. 2,3,52,3,5.

Solution. It is clear that any two numbers in the triplet are distinct (if p=qp=q, then p41p^{4}-1 does not divide qq). Let pp be the smallest of the numbers in the triplet. We know that the number p41=(p1)(p+1)(p2+1)p^{4}-1=(p-1)(p+1)\left(p^{2}+1\right) is divisible by qrq r. Note that p1p-1 is less than any of the prime numbers qq and rr, and therefore is coprime with them. Furthermore, the number p2+1p^{2}+1 cannot be divisible by both qq and rr, since p2+1<pp^{2}+1 < p, which is only possible if q=p+1q=p+1. Then one of the numbers pp and qq is even, and since it is prime, p=2,q=3p=2, q=3. Finally, rr is a prime divisor of the number p41=15p^{4}-1=15, different from q=3q=3, so r=5r=5.

It remains to check that the triplet 2,3,52,3,5 satisfies the conditions of the problem.

Comment. Only the correct answer -1 point.

The idea of choosing the smallest pp from the three prime numbers to investigate the divisibility of p41p^{4}-1 by qrq r is worth 1 point.

If the solution is correct but lacks the indication that the obtained triplet fits, 1 point is deducted.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.