Числа Мерсенна и Ферма — различия между версиями
Isaeva (обсуждение | вклад) |
Isaeva (обсуждение | вклад) |
||
| Строка 26: | Строка 26: | ||
'''Определение''' | '''Определение''' | ||
| − | '''Числа Ферма''' — числа вида <math>F_n=2^{2^n}+1</math>, где ''n'' — неотрицательное целое число. | + | '''Числа Ферма''' — числа вида <math>F_n=2^{2^n}+1</math>, где ''n'' — неотрицательное целое число. |
| + | |||
При <math>n = 0, 1, 2, 3, 4</math> числа Ферма простые: <math>3, 5, 17, 257, 65537</math>. | При <math>n = 0, 1, 2, 3, 4</math> числа Ферма простые: <math>3, 5, 17, 257, 65537</math>. | ||
Все числа Мерсенна и Ферма – взаимно простые. | Все числа Мерсенна и Ферма – взаимно простые. | ||
| + | |||
Необходимо отметить, что значения чисел Мерсенна и Ферма быстро растут. Это не позволяет использовать лишь их в качестве модуле СОК. | Необходимо отметить, что значения чисел Мерсенна и Ферма быстро растут. Это не позволяет использовать лишь их в качестве модуле СОК. | ||
| + | |||
| + | |||
| + | '''Операции над числами Мерсенна и Ферма''' | ||
Версия 13:25, 10 сентября 2014
При рассмотрении отдельных классов простых чисел значительный интерес представляет вопрос о простых числах специального вида, например, числа Мерсенна или числа Ферма.
Определение
Числа Мерсенна — числа вида 
, где 
— натуральное число.
Названы в честь французского математика Марена Мерсенна.
Иногда числами Мерсенна называют только числа 
с нечетными или простыми индексами n.
Множества простых чисел в этих последовательностях совпадают, а потому понятие простого числа Мерсенна не зависит от того, как именно определяются числа Мерсенна.
При простых значениях n = p число может оказаться простым, но может быть составным.
Например, при 
мы получаем простые числа Мерсенна: 
, а при 
числа 
- составные.
Свойства чисел Мерсенна
- Если является простым, то число n также простое. Обратное в общем случае неверно, наименьшим контрпримером является
.
- Любой делитель числа
для простого p имеет вид 2pk+1, где k — натуральное число (следствие малой теоремы Ферма).
Числа Мерсенна получили известность в связи с эффективным тестом простоты Люка — Лемера, благодаря которому простые числа Мерсенна давно удерживают лидерство как самые большие известные простые числа.
Определение
Числа Ферма — числа вида 
, где n — неотрицательное целое число.
При 
числа Ферма простые: 
.
Все числа Мерсенна и Ферма – взаимно простые.
Необходимо отметить, что значения чисел Мерсенна и Ферма быстро растут. Это не позволяет использовать лишь их в качестве модуле СОК.
Операции над числами Мерсенна и Ферма
