Матеріали для Нової української школи 1 клас - планування, розробки уроків, дидактичні та методичні матеріали, підручники та зошити

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

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

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

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

Більшість учених давнини вважали, що числа виду 2n - 1 є простими для простих n. І лише 1536 р. Регіусом була показана складність числа 2n - 1 = 2047 = 23 x 89. У 1603 р. Катаді перевірив простоту чисел 217- 1 і 219- 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-м простим числом Мерсенна. Воно дорівнює 224.036.583 і містить 7 235 733 знаки у десятковому записі і є найбільшим відомим простим числом на сьогодні.

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

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

Номер числа Мерсенна

Експонента n

n (2n-1)

Рік знаходження

Кількість

цифр

1

2

500 до н. е.

1

2

3

500 до н. е.

1

3

5

275 до н. е.

2

4

7

275 до н. е.

3

5

13

1456

4

6

17

1588

6

7

19

1588

6

8

31

1772

10

9

61

1883

19

10

89

1911

27

11

107

1914

33

12

127

1876

39

13

521

30 січня 1952

157

14

607

30 січня 1952

183

15

1279

26 червня 1952

386

16

2203

7 жовтня 1952

664

17

2281

9 жовтня 1952

687

18

3217

8 вересня 1957

969

19

4253

3 листопада 1961

1281

20

4423

3 листопада 1961

1332

21

9689

11 травня 1963

2917

22

9941

16 травня 1963

2993

23

11 213

2 червня 1963

3376

24

19 937

4 березня 1971

6002

25

21 701

30 жовтня 1978

6533

26

23 209

9 лютого 1979

6987

27

44 497

8 квітня 1979

13395

28

86 243

25 вересня 1982

25962

29

110 503

28 січня 1988

33 265

ЗО

132 049

19 вересня 1983

39751

31

216 091

1 вересня 1985

65050

32

756 839

1 квітня 1992

227 832

33

859 433

1 лютого 1994

258 716

34

1 257 787

1 398 269

2 976 221

3 021 377

6 972 593

13466917

20 996 011

3 вересня 1996

23 листопада 1996

1 листопада 1997

24 серпня 1998

378632

420921

895932

909 526

2 098960

4 053946

6320 430

35

36

37

38

1 червня 1999

39

14 листопада 2001

40

17 листопада 2003

41

24 036 583

15 травня 2004

7 235 733

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

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

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

хn - 1 = x r+s - 1 = (хs = 1 ) · (хs ·r-1) + (хs ·r-2) + ... + xs = 1) для довільного x.

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

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

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

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

Але

Приклад. Нехай р │ М31 (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, коли n2 = 2 (mod q). Маємо

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

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

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

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

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

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

n

1

2

3

4

5

6

7

8

9

10

11

12

σ(n)

1

3

4

7

6

12

8

15

13

18

12

28

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

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

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

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

Приклад.

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

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

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

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

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

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

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

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

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

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

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

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

σ(m) = 2k · М.

Оскільки m і М — дільники m, то 2k · М = σ(m)m + М = 2k · М. Адже σ(т) = т + М. Це означає, що m є простим і має лише два дільники: саме себе (m) і одиницю (М), звідки m = 2k - 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 одному з чисел

21 - 1 · (21 - 1), 23 - 1 · (23 - 1), 25 - 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 · (2p - 1) закінчується на 6 або 8.

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

Визначення. Для непарного n число Mn є простим тоді й тільки тоді, коли воно ділить Ln – 1, де Ln –1 = Ln 2-2 , L 1= 4.

Приклад.

М3 = 23 - 1 = 7 є дільником K2 = 14,

М5 = 25 —1=31 — дільник K4 = 37 634,

М4 = 24 - 1 = 15 не ділить K3 = 194.

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

l ← 4; m ← 13;

for i ← 1 to m - 2 do

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

i

1

2

3

4

5

6

7

8

9

10

11

12

Ki mod (2n - 1)

4

14

194

4870

3953

5970

1857

36

1294

3470

128

0









загрузка...