2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 док-во простоты числа
Сообщение02.05.2010, 08:58 
Всем привет! Подскажите, как лучше сделать это задание:

Существует ли такое целое неотрицательное $n$, что:

$22^n + 1$ - простое;
n представимо в виде $a^3-b^3$ ($a,b$ - натуральные)

Я решил его так:

$22^n + 1\equiv 0 $(mod p), $p= [22^n + 1, 1]$
$22^n\equiv -1 $(mod p)
$22^n\equiv -1^n $(mod p), n=1,3,5...
$22\equiv -1 $(mod p)$
$23\equiv 0 $(mod p)$

Отсюда $23$ - число простое, значит при $n=1,3,5...$ число $22^n + 1$ тоже будет простым...

Аналогично доказал для $n=a^3-b^3$. ($a-b=n, n=1,3,5...$)

Спасибо!

 
 
 
 Re: док-во простоты числа
Сообщение02.05.2010, 10:13 
Аватара пользователя
$22^n+1$ делится на $23$ для нечётных $n$. $22^2+1=5*97, 22^4+1=73*2309$. Тут компьютер нужен.

 
 
 
 Re: док-во простоты числа
Сообщение02.05.2010, 10:15 
чушь какая-то...
ответ $n=1$, а
$22^3+1=10649$ - не простое
$22^5+1=5153633$ - не простое
$22^7+1=2494357889$ - не простое
$22^9+1=1207269217793$ - не простое
$22^{11}+1=584318301411329$ - не простое
$22^{13}+1=282810057883082753$ - не простое
$22^{15}+1=136880068015412051969$ - не простое
ит.д. до 23 как минимум, дальше у меня на калькуляторе разряды кончились )

 
 
 
 Re: док-во простоты числа
Сообщение02.05.2010, 10:56 
Аватара пользователя
$a=3, b=1, n=26, 22^{26}+1$ делится на $5$. $a=4, b=2, n=56, 22^{56}+1$ делится на $17$. Продолжите эту последовательность и постарайтесь найти закономерность.

 
 
 
 Re: док-во простоты числа
Сообщение02.05.2010, 11:35 
Аватара пользователя
Устроили тут какую-то поездку через Бирюлёво в Дегунино. (Я, конечно, тоже так иной раз люблю, но.) Сразу про числа Ферма напомнить было не?
2 maikle:
Изображение

 
 
 
 Re: док-во простоты числа
Сообщение02.05.2010, 14:46 
Аватара пользователя
Можно попробовать расмотреть задачу факторизации многочлена $Z^n+1$ и показать, что, если у $n$ есть нечётный множитель, то этот многочлен факторизуем в кольце многочленов с целыми коэффициентами. Дальше подумайте, может ли степень двойки представить как разность кубов.

 
 
 
 Re: док-во простоты числа
Сообщение02.05.2010, 18:59 
)) эту задачу дали на олимпиаде в 9 классе, зная школьный курс (самые основы) доказать уже никак чтоли?

А с mod как-то можно ведь доказать? И да, увы, в 9 классе мы числа Ферма близко не рассматривали, как и не занимались вплотную теорией чисел...

 
 
 
 Re: док-во простоты числа
Сообщение02.05.2010, 19:31 
Аватара пользователя
Так смотрите мой предыдущий пост. Берём многочлен $Z^n+1$. Раскладываем его на множители с целыми коэфициентами (факторизуем). Теперь подставляем вместо $Z$ число 22, и получаем разложение числа $22^n+1$ на множители (не обязательно простые). Теперь вопрос - при каких $n$ это разложение возможно. Если $n$ нечётное число, то $Z^n+1$ делится на $Z+1$. Если $n=m*2^k$, то $Z^n+1$ делится на $Z^{2k}+1$. Осталось доказать, что степени многочленов, которые мы ещё не разложили (это степени двойки) нельзя представить в виде разности кубов... А попробуйте сами докончить доказательство.

 
 
 
 Re: док-во простоты числа
Сообщение02.05.2010, 19:32 
Можно.
Если у $n$ есть нечетный делитель, то ... Если нет, то $n$ является степенью числа ... Если число $a^3 - b^3$ является степенью, то, расладывая разность кубов на множители, получаем, что степенью является ...
Заполните пропуски, затем продолжим.

 
 
 
 Re: док-во простоты числа
Сообщение02.05.2010, 19:36 
А чего париться то?) 23 - число простое, и n представимо в виде разности кубов))

Цитата:
факторизуем


Это явно не знает не продвинутый ученик))

 
 
 
 Re: док-во простоты числа
Сообщение02.05.2010, 19:44 
Аватара пользователя
мат-ламер прикалывается. Факторизовать - значит попросту разложить на множители. Да вон он уже и пояснил.
maikle в сообщении #314995 писал(а):
23 - число простое, и n представимо в виде разности кубов

Можно вот это место чуть-чуть поподробнее?

 
 
 
 Re: док-во простоты числа
Сообщение02.05.2010, 20:11 
Цитата:
Можно вот это место чуть-чуть поподробнее?


Обшибся, извините. Все равно короче не хочу читать про факторизацию многочленов, пощелкал ссылки и закрыл :D

Через mod все-тки можно как-нить того? :mrgreen:

 
 
 
 Re: док-во простоты числа
Сообщение02.05.2010, 20:14 
Аватара пользователя
Под mod Вы, судя по первому сообщению, понимаете что-то своё, нам неведомое.

 
 
 
 Re: док-во простоты числа
Сообщение02.05.2010, 20:16 
Я хотел написать, что не так применил свойство с mod, в свойствах речь шла об "операции со степенями и модами " наоборот. В общем это уже неважно, просто 1ый пост не смог отредактировать(

 
 
 [ Сообщений: 14 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group