Maths Olympiad Prep

Library / /12 of 57

Number theory Difficulty 6.0 National olympiad Prove it Russia

Find all triples of prime numbers (p,q,r)(p, q, r) such that pqr41pq \mid r^4 - 1, prq41pr \mid q^4 - 1, and qrp41qr \mid p^4 - 1.

Найдите все тройки простых чисел p,q,rp, q, r такие, что четвёртая степень любого из них, уменьшенная на 1, делится на произведение двух остальных.

Solution

Ответ. 2,3,52, 3, 5.

Ясно, что любые два числа тройки различны (если p=qp = q, то p41p^4 - 1 не делится на qq). Пусть для определённости pp — наименьшее из чисел тройки. Нам известно, что число p41=(p1)(p+1)(p2+1)p^4 - 1 = (p - 1)(p + 1)(p^2 + 1) делится на qrqr. Заметим, что p1p - 1 меньше любого из простых чисел qq и rr, а значит, взаимно просто с ними. Далее, число p2+1p^2 + 1 не может делиться на оба числа qq и rr, так как p2+1<(p+1)(p+1)<qrp^2 + 1 < (p + 1)(p + 1) < qr. Значит, p+1p + 1 делится на одно из них (для определённости, на qq). Поскольку q>pq > p, это возможно лишь при q=p+1q = p + 1. Тогда одно из чисел pp и qq чётно, а поскольку оно простое, то p=2,q=3p = 2, q = 3. Наконец, rr является простым делителем числа p41=15p^4 - 1 = 15, отличным от q=3q = 3, значит, r=5r = 5.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.