Решение 1.
Предположим, что множество состоит только из простых чисел. Тогда все числа из множества нечётные(так как любое число вида составное при ). Возьмём в множестве два произвольных числа Если даёт остаток при делении на то также даёт остаток Тогда делится на 3 и по нашему предположению не может принадлежать множеству Значит, в этом случае множеству принадлежит число Аналогично если даёт остаток при делении на то также даёт остаток составное и тогда в этом случае множество должно содержать число
Если множество содержит хотя бы одно простое число дающее остаток при делении на то в множестве как мы установили, содержится число вида дающее остаток Тогда число тоже принадлежит Заметим, что это число даёт при делении на тот же остаток, что и число Но это число делится на по малой теореме Ферма, значит, оно составное.
Аналогично, если простое число даёт остаток при делении на то в множестве содержится число которое по тем же причинам делится на
Решение 2.
Предположим противное. Как и в первом решении установим, что если (mod ) принадлежит то также принадлежит В частности, в есть числа, сравнимые как с так и с по модулю
Рассмотрим простые числа и из Тогда в содержится простое число

Следовательно, делится на Пусть Тогда число

делится на поскольку по малой теореме Ферма и, значит,

Таким образом, число принадлежит и является составным. Противоречие.