док-во простоты числа

[maikle]

Всем привет! Подскажите, как лучше сделать это задание:

Существует ли такое целое неотрицательное $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...$)

Спасибо!

[мат-ламер]

$22^n+1$ делится на $23$ для нечётных $n$. $22^2+1=5*97, 22^4+1=73*2309$. Тут компьютер нужен.

[VoloCh]

чушь какая-то...
ответ $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 как минимум, дальше у меня на калькуляторе разряды кончились )

[мат-ламер]

$a=3, b=1, n=26, 22^{26}+1$ делится на $5$. $a=4, b=2, n=56, 22^{56}+1$ делится на $17$. Продолжите эту последовательность и постарайтесь найти закономерность.

[ИСН]

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

[мат-ламер]

Можно попробовать расмотреть задачу факторизации многочлена $Z^n+1$ и показать, что, если у $n$ есть нечётный множитель, то этот многочлен факторизуем в кольце многочленов с целыми коэффициентами. Дальше подумайте, может ли степень двойки представить как разность кубов.

[maikle]

)) эту задачу дали на олимпиаде в 9 классе, зная школьный курс (самые основы) доказать уже никак чтоли?

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

[мат-ламер]

Так смотрите мой предыдущий пост. Берём многочлен $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$. Осталось доказать, что степени многочленов, которые мы ещё не разложили (это степени двойки) нельзя представить в виде разности кубов... А попробуйте сами докончить доказательство.

[Cave]

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

[maikle]

А чего париться то?) 23 - число простое, и n представимо в виде разности кубов))

Цитата:

факторизуем

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

[ИСН]

мат-ламер прикалывается. Факторизовать - значит попросту разложить на множители. Да вон он уже и пояснил.

maikle в сообщении #314995 писал(а):

23 - число простое, и n представимо в виде разности кубов

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

[maikle]

Цитата:

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

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

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

[ИСН]

Под mod Вы, судя по первому сообщению, понимаете что-то своё, нам неведомое.

[maikle]

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