Теория чисел на Турломе

Докажем, что в общем случае при не являются волшебными числа только вида , где — простое.

Для этого разберём три случая: когда является простым, когда является простым, и когда ни , ни не являются простыми (в частности, если нечётно, то не является простым).

_________________________________________________________________________________________________________________________________________________________________________________

Первый случай. Если является простым. Рассмотрим выражение

по модулю Утверждается, что среди слагаемых в этой сумме встретятся все возможные ненулевые остатки по модулю . Так как различных ненулевых остатков по модулю ровно и слагаемых столько же достаточно показать, что все слагаемые дают различные остатки по модулю . Это действительно так, потому что в противном случае для некоторы и таких, что было бы верно сравнение

Но перенеся в этом сравнении всё в левую часть, получаем

что невозможно, так как все множители в произведении не делятся на , а — простое. Полученное противоречие доказывает, что слагаемые являются всеми возможными остатками по модулю , а значит, им сумма равна , то есть кратна , так как простое, большее а следовательно, нечётно.

_________________________________________________________________________________________________________________________________________________________________________________

Второй случай. Если является простым. Обозначим через тогда Заметим, что среди чисел от до есть только одно, кратное : это само число . Тогда при раскрытии скобок в выражении

все слагаемые кроме будут кратны а это слагаемое — не будет. Значит, и вся сумма не будет кратна , а следовательно, и , то есть . Значит, в этом случае число магическим не является.

_________________________________________________________________________________________________________________________________________________________________________________

Tретий случай. Если ни ни не являются простыми. В этом случае можно представить в виде произведения (т. к. непростое), причём оба множителя будут больше (так как либо , поделённое на любой нечётный простой делитель будет больше двойки, либо — степень двойки, но в силу степень двойки хотя бы четвёртая, и значит, , где оба множителя больше ). То есть для некоторых верно . Тогда раскрывая скобки в выражении

получаем слагаемые вида , где , и два слагаемых

Во всех слагаемых первого вида в произведении содержатся множители и , а значит, после сокращения на оставшееся произведение будет делиться на . Теперь заметим, что . Тогда в случае во втором слагаемом в произведении содержатся различные множители а значит, после сокращения на останется произведение , кратное . Если же , то , но тогда число и кратно . Аналогично доказывается, что последнее, третье слагаемое, кратно , а значит, число является волшебным, так как все слагаемые кратны .

_________________________________________________________________________________________________________________________________________________________________________________

Осталось заметить, что числами, для которых их половина является простым числом, являются те и только те, что перечислены как исключённые в ответе.