Конкурсная задача ММ56 (12 баллов)

Назовем трехпарным число, допускающее представление в виде суммы трех взаимно простых натуральных слагаемых, любые два из которых не взаимно просты. Конечно ли множество натуральных чисел, не являющихся трехпарными?

Решение

Пусть p < q < r - три простых числа. Докажем, что все натуральные числа взаимно простые с pqr, начиная с некоторого, будут трехпарными.

Приведу доказательство этого факта в изложении Виктора Филимоненкова.

Докажем, что любое число n, которое больше p²qr и взаимно просто с pqr, будет трехпарным.
Действительно, рассмотрим числа вида n-xqr. Поскольку p и qr взаимно просты, и n не делится на p, найдется такое целое положительное x < p, что n-xqr делится на p. Пусть n-xqr = mp. В силу того, что n > p²qr и x < p, имеем: m > (p-1)qr, причем m не делится на q и r.
Поскольку q и r взаимно просты, найдется такое целое положительное y < r, что m-yq делится на r. Поскольку r > p > x, и r - простое, то r и x взаимно просты, а, значит, остатки от деления на x чисел вида y+kr при k = 0,1,…x-1 различны. Значит, среди этих остатков есть 1. Значит, для такого k число w = y+kr взаимно просто с x. Но поскольку m-yq делится на r, то и m-wq = m-yq-krq делится на r. При этом m-yq-krq > (p-1)qr-yq-kqr > (p-1)qr-qr-(p-2)qr = 0, то есть m = wq+zr, причем w,z > 0. Окончательно имеем: n = xqr + wpq + zpr, причем эти три слагаемых взаимно просты, поскольку xqr и wpq имеют наибольший общий делитель q (все остальные множители в этих слагаемых взаимно просты по построению), а zpr не делится на q (иначе бы и n делилось на q). Таким образом, n трехпарно.

С помощью полученной оценки легко доказать конечность множества чисел, не являющихся трехпарными.
В самом деле, для достаточно большого числа n, обязательно найдутся три простых числа p, q r, не являющиеся его делителями такие, что n > p² qr. Не сложно проверить, что это соотношение будет выполняться для всех n, больших 120120.

Oбсуждение

Полученная в решении верхняя граница для чисел, не являющихся трехпарными, разумеется, завышена.
Обозначим через g(p,q,r) самое большое натуральное число, не представимое в виде xp + yq + zr со взаимно простыми слагаемыми. Можно показать, что при p = 2 g(p,q,r) = 2pqr - pq - pr - qr, что совпадает со значением функции Frob(pq,pr,qr) (см. марафонскую задачу ММ37). Если меньший из аргументов g принадлежит множеству {3, 5, 7}, то g(p,q,r) = 3pqr - pq - pr - qr. Точной формулы для g(p,r,r) в общем случае я не знаю, но для каждой конкретной тройки аргументов значение находится (и обосновывается) не слишком сложно. По-видимому, g(p,q,r) не превосходит pqr✔p.
Нахождение g(p,q,r) для небольших значений p, q, r позволяет снизить найденную верхнюю границу до 13860 (наибольшее число, не превосходящее g(p,q,r) для наименьших простых p, q, r, не являющихся его делителями).
Новая граница не слишком велика. Поэтому не трудно сделать перебор и найти все 156 чисел, не являющихся трехпарными. Вот они:
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 50, 51, 52, 54, 56, 57, 58, 60, 62, 63, 64, 66, 68, 70, 72, 74, 75, 76, 78, 80, 81, 82, 84, 88, 90, 94, 96, 98, 100, 102, 104, 105, 108, 110, 112, 114, 120, 124, 126, 130, 132, 138, 140, 142, 144, 150, 154, 156, 160, 162, 165, 168, 170, 174, 180, 186, 192, 198, 200, 204, 210, 216, 220, 228, 234, 240, 246, 252, 258, 264, 270, 276, 280, 288, 294, 300, 306, 330, 336, 348, 360, 372, 378, 390, 420, 450, 462, 474, 480, 504, 510, 540, 546, 600, 630, 660, 672, 690, 720, 750, 780, 840, 924, 930, 990, 1050, 1140, 1260, 1320, 1470, 1680, 2310, 2730}

Влад Франк прислал решение задачи, обобщающей задачу ММ56. Он доказал конечность множества натуральных чисел, не допускающих представления в виде суммы k+1 взаимно простых слаuаемых, любые k из которых не взаимно просты.

Награды

За правильное решение этой задачи Виктор Филимоненков получает 12 призовых баллов, а Влад Франк - 15 призовых баллов.

Эстетическая оценка задачи - 4 балла

---