Регистрация    Вход    Форум    Поиск    FAQ   alexlarin.net

Список форумов » Интересные задачки




 Страница 1 из 1 [ Сообщений: 2 ] 



Автор Сообщение
 Заголовок сообщения: Задача Сендерова 3.2
 Сообщение Добавлено: 30 ноя 2014, 08:22 
Не в сети
Аватар пользователя

Зарегистрирован: 31 янв 2011, 17:37
Сообщений: 4119
Откуда: Санкт-Петербург
Если число `a=2^(2k)+2^k+1` не является делителем числа `2^(2^k)-1` , то а - составное. Докажите это.

_________________
Сопротивление бесполезно.


Вернуться наверх 
 Заголовок сообщения: Re: Задача Сендерова 3.2
 Сообщение Добавлено: 06 сен 2015, 12:44 
Не в сети

Зарегистрирован: 14 фев 2012, 19:11
Сообщений: 339
Опечатка: вместо $2^{2^k}-1$ должно быть $2^{2^k+1}-1$.

Для решения задачи достаточно доказать, что если $a$ --- простое число, то $k$ должно быть степенью тройки. Последнее утверждение верно, так как иначе многочлен $x^{2k}+x^k+1$ разлагался бы на множители с целыми коэффициентами.

Такой способ решения задачи заодно показывает, что обратное (к сформулированному в задаче) утверждение неверно: маловероятно, что все числа вида $P(n)=2^{2 \cdot 3^n}+2^{3^n}+1$ будут простыми (по аналогии с числами Ферма $F(n)=2^{2^n}+1$). И действительно, числа $P(0)$, $P(1)$, $P(2)$ --- простые, а дальше неизвестно, есть ли ещё простые. Критерием простоты числа $P(n)$ является выполнимость сравнения $5^{(P(n)-1)/2} \equiv -1$ по модулю $P(n)$, однако, как и аналогичный критерий простоты чисел Ферма, этот критерий малоэффективен на практике.


Вернуться наверх 
Показать сообщения за:  Сортировать по:  
 
 Страница 1 из 1 [ Сообщений: 2 ] 





Кто сейчас на форуме

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

 
 

 
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти: