Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Простые числа Мерсенна и Ферма

Формулы Миллса, Райта и другие подобные формулы остались изолированными фактами, не приведшими к новым результатам. Однако в других случаях возможность представить некоторые простые числа в том или ином специальном виде имеет неожиданные и глубокие следствия.

Рассмотрим сейчас две формулы, имеющие совсем простой вид:

p = 2n – 1, (8)
p = 2n + 1. (9)

 

Очевидно, что формула (8) не всегда даёт простые числа; например, если n — составное число, n = kl, k>1, l>1, то p делится на 2k — 1 и на 2l — 1. Но и при простом n получающееся по формуле (8) число может оказаться составным:

211 – 1 = 2047 = 23 · 89.

 

Простые числа, получающиеся по формуле (8), называются числами Мерсенна в честь Марена Мерсенна, который ещё в 1664 году указал все простые значения n, не превосходящие 257, для которых, по его мнению, формула (8) даёт простые числа. Однако Мерсенн не дал доказательства; впоследствии выяснилось, что его предсказание было частично ошибочным.

Интерес к числам Мерсенна вызван их связью с так называемыми совершенными числами — числами, равными сумме всех своих делителей, отличных, конечно, от самого числа. Ещё Евклид доказал (докажите и вы), что если простое число p имеет вид, указанный в формуле (8), то число p(p+1)/2 является совершенным. Например,

3 = 22 – 1, 7 = 23 – 1

 

простые числа, и соответственно

6 = (3 · 4)/2 = 1 + 2 + 3,
28 = (7 · 8)/2 = 1 + 2 + 4 + 7 + 14

 

— совершенные числа. Спустя несколько столетий Леонард Эйлер доказал (попробуйте и здесь свои силы), что все чётные совершенные числа имеют вид, указанный Евклидом. Таким образом, вопрос, конечно или бесконечно множество чётных совершенных чисел, свёлся к вопросу, конечно или бесконечно множество простых чисел Мерсенна, то есть к вопросу, реализует ли формула (8) нашу программу-минимум. Ответ на этот вопрос не известен до сих пор 3.

Формула (9) также не всегда даёт простые числа, например, если n имеет простой нечётный делитель m, то p делится на 2n/m + 1, а если n само нечётно, то p делится на 3. Таким образом, вместо n в формулу (9) имеет смысл подставлять только 0 и степени числа 2. При n=0, 20, 21, 22, 23 и 24 формула (9) действительно даёт простые числа, и Пьер Ферма, живший в XVII веке, высказал предположение, что и при любом n вида 2k формула (9) даёт простое число; в его честь простые числа вида 2^(2^k)+1 получили название чисел Ферма. Гипотезу Ферма опроверг Эйлер, указавший, что число 2^(2^5)+1 делится на 641. В настоящее время известно несколько значений n вида 2k, при которых по формуле (9) получаются составные числа, но не найдено ни одного нового простого числа Ферма, отличного от указанных выше.

Простые числа Ферма обнаруживают неожиданную связь с геометрией. Выдающийся немецкий математик Карл Фридрих Гаусс доказал, что правильный p-угольник можно построить циркулем и линейкой при простом p в том и только том случае, когда p — число Ферма. Более общий результат таков: правильный m-угольник допускает построение циркулем и линейкой тогда и только тогда, когда m = 2s· p1 p2 ...pk , где p1, p2,..., pk — попарно различные простые числа Ферма.

 

<== предыдущая лекция | следующая лекция ==>
Теорема Е. М. Райта | Скатерть Улама
Поделиться с друзьями:


Дата добавления: 2014-01-03; Просмотров: 571; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.011 сек.