среда, 5 августа 2015 г.

Волшебство составных чисел Мерсенна

Числами Мерсенна \(M_n\) называются числа вида \(2^n-1\), где \(n\) - натуральное число. 

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

Но сегодня мы займемся исследованием вопроса, относящегося к свойствам составных чисел Мерсенна.

А именно, правда ли, что для любого натурального \(n\) число \(M_{3628800 \cdot n}\) делится на 5643118635?


Ответ на этот вопрос можно легко получить, используя следующую теорему:

Теорема. Пусть \(n\) - некоторое натуральное число и \(d\) - любой из делителей числа мерсенна \(M_n\). Тогда для любого натурального \(m\) число \(M_{n \cdot m}\) также делится на \(d\).

Доказательство построим по индукции.  В самом деле, для \(m=1\) утверждение очевидно. Предполагая, что оно верно для некоторого m, рассмотрим цепочку тождеств

\(M_{n \cdot (m+1)} = (M_{n \cdot m}+1) \cdot (M_n +1) -1 = (d*q_1+1)(d*q_2+1)-1 = \)
\(=d*(d*q_1*q_2 + q_1 + q_2)\),

из которой следует, что \(d\) является также делителем числа \(M_{n \cdot (m+1)}\).

Из доказанной теоремы следует:

Следствие 1. Пусть \(D(n,1)\) - множество делителей числа \(M_n\), и \(D(n,m)\) - множество делителей числа \(M_{n \cdot m}\), где  \(m\) - произвольное натуральное число. Тогда \(D(n,1) \subseteq D(n,m)\).

Доказательство очевидно. 

Покажем теперь, что если \(n = d_1 \cdot d_2 \cdot ... \cdot d_q\), то для любого \(i \in \{1,...,q\}\) число \(M_n\) делится  на \(M_{d_i}\).

Действительно, для любого \(d_i\) верно \(n = d_i*Q\). Но тогда

\(M_{d_i \cdot Q} = (M_{d_i}+1)^Q-1 = \)
\(= M_{d_i}*((M_{d_i}+1)^{Q-1} + (M_{d_i}+1)^{Q-2} + ... + 1)\), 

и утверждение доказано.

Таким образом, имеет место 

Следствие 2. Если  \(n = d_1 \cdot d_2 \cdot ... \cdot d_q\) то для любого натурального \(m\) \( (D(d_1,1) \cup D(d_2,1) \cup … \cup D(d_q,1)) \subseteq D(n,m)\).

Имеют место следующие утверждения:

\(M_2 \equiv 0 \pmod {3} \);

\(M_3 \equiv 0 \pmod {7} \);

\(M_4 \equiv 0 \pmod {5} \);

\(M_5 \equiv 0 \pmod {31} \);

\(M_7 \equiv 0 \pmod {127} \);

\(M_8 \equiv 0 \pmod {17} \);

\(M_9 \equiv 0 \pmod {73} \);

\(M_{10} \equiv 0 \pmod {11} \).


В силу доказанного выше, для любого натурального \(n\) \(\{3,7,5,31,127,17,73,11\} \subseteq D(10!, n)\).

Другими словами, \(M_{3628800 \cdot n} \equiv 0 \pmod{5643118635}\), что и требовалось доказать.