МАТЕМАТИКА Й МАТЕМАТИЧНА СТАТИСТИКА - Золота колекція рефератів - 2018

ЧИСЛА МЕРСЕННА

У роботі наводяться останні результати щодо пошуку великих простих чисел Мерсенна, їхніх властивостей і зв’язків з досконалими числами. Йдеться про існуючі проблеми, пов’язані з числами Мерсенна.

Визначення. Числами Мерсенна називаються числа виду М_n = 2ⁿ - 1.

Більшість учених давнини вважали, що числа виду 2ⁿ - 1 є простими для простих n. І лише 1536 р. Регіусом була показана складність числа 2ⁿ - 1 = 2047 = 23 x 89. У 1603 р. Катаді перевірив простоту чисел 2¹⁷- 1 і 2¹⁹- 1 і помилково стверджував простоту чисел для степенів 23, 29, 31 і 37.

У 1640 р. Ферма довів Катаді, що він помилявся щодо простоти чисел для степенів 23 і 37, а Ейлер 1738 р. довів складність числа для n = 29. Пізніше Ейлер показав, що для n = 31 Катаді мав рацію.

Французький чернець Марен Мерсенн (1588-1648) довів, то лише при n = 2 ,3, 5, 7, 13, 17, 19,31, 67,127, 257 числа виду 2n - 1 є простими (перевірка зроблена для всіх n < 258).

На Інтернет-сторінціі WWW.mersenne.org проводиться пошук великих чисел Мерсенна. Останнє число, знайдене в рамках проекту Джошем Фіндлі 15 травня 2004 р., стало 41-м простим числом Мерсенна. Воно дорівнює 2^24.036.583 і містить 7 235 733 знаки у десятковому записі і є найбільшим відомим простим числом на сьогодні.

40-е просте число Мерсенна було знайдено Михайлом Шафером 17 листопада 2003 р. Воно дорівнює 2^20.996.011 і містить 6 320 430 знаків у десятковому записі.

Поруч наведена таблиця простих чисел Мерсенна, включаючи їхній номер, рік знаходження й кількість цифр у десятковому представленні.

ВЛАСТИВОСТІ ЧИСЕЛ МЕРСЕННА

Теорема. Якщо для деякого натурального n значення 2ⁿ - 1 є простим, то n також є. простим.

Доведення. Якщо n = r · s — складене, то

хⁿ - 1 = x ^r+s - 1 = (х^s = 1 ) · (х^{s ·r-1}) + (х^{s ·r-2}) + ... + x^s = 1) для довільного x.

Звідки 2ⁿ - 1 буде складеним.

Теорема. Нехай р і q — непарні прості числа. Якщо р │ М (р ділить М_q), то р = 1(mod q)I p = ±1 (mod 8).

Доведення. Оскільки р │ M_q, то p│2q - 1 або 2q = 1 (mod р). Тобто порядок 2 ділить q: ord(2) │ q. Але q — все ж ord(2) = q. За теоремою Ферма 2^p-1 = 1 (mod р), тобто ord(2) │р - 1 або q │p - 1. Оскільки p - 1 — парне, то р - 1 = 2 · k · q для деякого k. У такий спосіб доведена перша рівність: р = 1 (mod q). З останньої рівності маємо:

Таким чином, 2 є квадратичним надлишком за модулем р.

Але

Приклад. Нехай р │ М₃₁ (q = 31). Тоді

Розв’язавши систему рівнянь, одержимо р = 1 (mod 248) або p = 63 (mod 248)

Теорема. Нехай р = 3 (mod 4) є простим. Виходить, 2 · р + 1 буде простим тоді й тільки тоді, коли 2 · р + 1 │М_р.

Доведення.

Необхідність. Нехай q = 2 · р + 1 — просте. Тоді q = 7 (mod 8) і за критерієм Ейлера, 2 є квадратичною остачею за модулем q. Тобто існує таке n, коли n² = 2 (mod q). Маємо

Достатність. Нехай 2 · p + 1 │ M_p. але 2 · p + 1 є складеним. Нехай q — найменший простий дільник 2 · р + 1.

Тоді q │ М_р або q │ 2ⁿ - 1, 2^p = 1 (mod р). Останнє означає, що ord(2) = р. Оскільки р просте, то оrd1(2) = р. За теоремою Ферма 2^{q - 1} = 1 (mod q) або ord(2) | q - 1. З останніх рівностей випливає, що р │ q - 1. Звідси можна встановити, що р < q.

Оскільки q — найменший простий дільник числа 2 · р + 1, то (2 · р + 1) + 1 > q². Але встановлено, що q² > р². Маємо (2 · р + 1) + 1 > р², що є протиріччям, оскільки р > 2.

Наслідок. Якщо р = 3 (mod 4) і 2 · р + 1 обидва прості, то або р = 3, або М_р складене.

ДОСКОНАЛІ ЧИСЛА Й ЧИСЛА МЕРСЕННА

Визначення. Позначимо через о(n) суму дільників числа n.

Визначення. Число називається досконалим, якщо воно подвоєне дорівнює сумі своїх дільників: σ(n) = 2 · n. Наприклад, числа 6 і 28 — досконалі, оскільки

2 — 6 = 1 + 2 + 3 + 6 = 12,2 · 28 = 1+2 + 4 + 7 + 14 + 28.

Якщо р — просте, то

Функція σ є мультиплікативною: σ(n · т) = σ(n) · σ(m).

Приклад.

Теорема. Якщо для деякого k число 2^k - 1 є простим, то число 2^{k - 1} · (2^{k - 1}) є досконалим. Усі парні досконалі числа мають вигляд 2^{k - 1} · (2^{k - 1}) для деякого натурального k.

Доведення. Позначимо р = 2^k - 1, n = 2^{k - 1} · (2^{k - 1})/

Щоб довести досконалість числа n, досить показати: σ(n) = 2 · n. Оскільки р є простим, а функція σ є мультиплікативною, то σ(р) = р + 1 = 2^k,

σ(n) = σ(2^{k - 1}) · σ(р) = (2^{k - 1}) · 2k = 2 · n,

що й доводить досконалість числа n.

Нехай досконале число n має вигляд 2^{k - 1} · т, де т — непарне натуральне число. З мультиплікативності функції маємо

σ(n) = σ(2^{k - 1}) · σ(m) = (2^{k- 1}) · σ(m).

Оскільки n є досконалим, то

σ(n) = 2· n = 2^k · m.

Порівнюючи праві частини останніх двох рівностей, маємо

(2^k - 1) · σ(m) = 2^k · m

Тобто 2^k - 1 ділить m. Нехай т = (2^k- 1) · М. Підставивши його в останнє рівняння й скоротивши на (2^k - 1), одержимо

σ(m) = 2^k · М.

Оскільки m і М — дільники m, то 2^k · М = σ(m)m + М = 2^k · М. Адже σ(т) = т + М. Це означає, що m є простим і має лише два дільники: саме себе (m) і одиницю (М), звідки m = 2^{k - 1} — просте.

Теорема. Якщо скласти цифри будь-якого парного досконалого числа (крім 6), потім знову скласти цифри й у такий спосіб далі продовжувати процес, то одержимо одиницю.

Доведення. Позначимо через s(n) суму цифр числа n. За ознакою подільності на 9 маємо s(n) = 72(mod 9). Для доказу теореми досить показати, що довільне досконале число при діленні на 9 дає остачу 1. Якщо n — досконале, то воно має вигляд

n = 2 ^{p - 1} · (2р - 1), де р — просте. Адже р дорівнює або 2, або 3, або при діленні на 6 дає залишки 1 чи 5 (будь-яке просте число р має вигляд 6 · т ± 1, де m — натуральне число). Випадок р = 2 (n= 6) ми вилучили з розгляду. Якщо розглядати послідовність ступенів двійки за модулем 9, то вона матиме період 6 (тому що 26 є 1 (mod 9)). Тоді число n буде конгруентним за модулем 9 одному з чисел

2^{1 - 1} · (21 - 1), 2^{3 - 1} · (23 - 1), 2^{5 - 1} · (25 - 1). Але всі вони дорівнюють 1.

Теорема. Кожне парне досконале число в десятковому записі завжди закінчується або цифрою 6, або цифрою 8.

Доведення. Досконале число n має вигляд 2 ^{p - 1} · (2р - 1). Десятковий запис 2 ^{p - 1} може закінчуватися на 2, 4, 8, 6, а відповідне число 2 ^p - 1 — цифрами 3, 7, 5, 1. Вираз 2 ^{p - 1} закінчується 8, лише коли р = 4 · k (р — складене), тому цей випадок вилучаємо з розгляду. Таким чином, добуток 2 ^{p - 1 ·} (2^p - 1) закінчується на 6 або 8.

ТЕСТ ЛЮКА-ЛЕМЕРА

Визначення. Для непарного n число M_n є простим тоді й тільки тоді, коли воно ділить L_{n — 1}, де L_{n —1} = L_n ^2-2 , L ₁= 4.

Приклад.

М₃ = 23 - 1 = 7 є дільником K₂ = 14,

М₅ = 25 —1=31 — дільник K₄ = 37 634,

М₄ = 24 - 1 = 15 не ділить K₃ = 194.

Приклад. Перевіримо, чи є простим число M₁₃ = 213 - 1. Програма перевірки за тестом Люка-Лемера має вигляд

l ← 4; m ← 13;

for i ← 1 to m - 2 do

l ←(l · l - 2) mod (2^m- 1).