Решение задачи 386

Условие:

Найдите все такие тройки простых чисел, что произведение любых двух из них при делении на третье даёт остаток 1.

Решение:

Во-первых заметим, что все три числа различные. Действительно, пусть наша тройка это p, p, q. Тогда pq никак не может давать остаток 1 при делении на p. Обозначим искомую тройку через p, q, r. Без ограничения общности считаем, что p<q<r. Запишем условие:

pq−1 делится на r,
pr−1 делится на q,
qr−1 делится на p.

Отсюда следует, что pq+qr+pr−1 делится на каждое из чисел p, q, r. Но, так как p, q, r попарно взаимно просты, то pq+qr+pr−1 делится на pqr. Так как каждое из чисел p, q, r положительное, то pq+qr+pr>pqr. Покажем, что p=2. Пусть p>2, то есть p хотя бы 3, тогда pqr≥3qr. Также нетрудно видеть, что pq+qr+pr<qr+qr+qr=3qr. Противоречие, значит p=2. Опять запишем условие:

2q−1 делится на r,
2r−1 делится на q,
qr−1 делится на 2 (это условие ничего дает, так как оно утверждает, что четное число делится на 2).

Аналогично предыдущим рассуждениям получаем, что 2q+2r−1 делится на qr и 2q+2r>qr. Покажем, что q=3. Пусть q>3, то есть q хотя бы 5, тогда qr≥5r. Снова нетрудно видеть, что 2q+2r<2r+2r=4r. Опять пришли к противоречию, значит q=3. Возвращаясь к условию, получаем, что 2*3−1=5 делится на r, значит r=5. Нетрудно видеть, что остальные два условия тоже выполняются: 2*5−1=9 делится на 3, 3*5−1=14 делится на 2.

Ответ: (2,3,5) -- единственная тройка.