Простая задача по теории чисел

[vatrushka]

Нужно доказать что $3^{(3^n)} + 1$ имеет $2n+ 1$ делитель.
$UPD$
Точнее надо доказать, что это произведение не менее чем $2n+ 1$ простых делителей.
Сперва я заметил что это сумма кубов и можно разложить

$$3^{(3^n)} + 1 = (3^{3^{(n-1)}} + 1) \cdot ( {{(3^{3^{(n-1)}})}^2} - (3^{3^{(n-1)}}) + 1)$$

Первая скобка это исходная, только степень $n$ на $1$ ниже
Значит можно применить эту операцию снова.
Итого, применяя ее $n$ раз мы разложим на произведение вида
$4 \cdot \displaystyle{ \prod_{k=1}^n }( (3^{3^{(k-1)}})^2 - (3^{3^{(k-1)}}) + 1) $
Итого, мы имеем $n + 1$ делитель
Надо доказать что их $2 \cdot n + 1$
Я не знаю что делать дальше.
Вероятно, надо показать как то что каждая из этих скобок в произведении не простая, тогда выходит что каждая скобка дает 2 делителя и все хорошо,
но как показать это я не знаю.
Подскажите

[Sasha2]

Эти скобки и есть остальные делители.

[grizzly]

vatrushka в сообщении #1449826 писал(а):

Я не знаю что делать дальше.

В таких случаях всегда полезно проверить делимость на самые малые простые. На 2, например.

[vatrushka]

Sasha2 в сообщении #1449830 писал(а):

Эти скобки и есть остальные делители.

Какие эти? В итоге остается произведение $n$ скобок....

-- 31.03.2020, 14:30 --

grizzly в сообщении #1449834 писал(а):

vatrushka в сообщении #1449826 писал(а):

Я не знаю что делать дальше.

В таких случаях всегда полезно проверить делимость на самые малые простые. На 2, например.

В том то и проблемма что я не очень понимаю на что они делятся
На 2 не делится, на 3 тоже
Вообще $3^2 - 3 + 1$ это простое вообще говоря

[nnosipov]

vatrushka в сообщении #1449826 писал(а):

Сперва я заметил что это сумма кубов и можно разложить

$$3^{(3^n)} + 1 = (3^{3^{(n-1)}} + 1) \cdot ( {{(3^{3^{(n-1)}})}^2} - (3^{3^{(n-1)}}) + 1)$$

А теперь можно было бы заметить, что сомножители в правой части взаимно просты, и рассуждать по индукции.

[vatrushka]

[/quote]А теперь можно было бы заметить, что сомножители в правой части взаимно просты, и рассуждать по индукции.[/quote]
А почему?

[nnosipov]

vatrushka
На самом деле взаимная простота сомножителей не нужна, это я погорячился (но она действительно имеет место, можете считать это дополнительным полезным упражнением). Важно, что второй сомножитель просто есть.

[vatrushka]

nnosipov в сообщении #1449849 писал(а):

vatrushka
На самом деле взаимная простота сомножителей не нужна, это я погорячился (но она действительно имеет место, можете считать это дополнительным полезным упражнением). Важно, что второй сомножитель просто есть.

Так а почему он есть?
Я вот этого как раз не понимаю.....

-- 31.03.2020, 15:05 --

Я уточнил
Да, является произведением не менее чем $2n + 1$ простых чисел (не обязательно различных)

[nnosipov]

vatrushka в сообщении #1449852 писал(а):

Так а почему он есть?

Вы же его написали, вот он и есть.

И присоединяюсь к пожеланию уточнить, о каких именно делителях идет речь в задаче.

[vatrushka]

Я уточнил
Да, является произведением не менее чем $2n + 1$ простых чисел (не обязательно различных)

[nnosipov]

vatrushka в сообщении #1449852 писал(а):

не менее чем $2n + 1$ простых чисел (не обязательно различных)

Тогда это совсем другое дело. Ключевое слово: простых.

Ну, вот теперь, я думаю, взаимная простота сомножителей пригодится.

[vatrushka]

nnosipov в сообщении #1449857 писал(а):

vatrushka в сообщении #1449852 писал(а):

не менее чем $2n + 1$ простых чисел (не обязательно различных)

Тогда это совсем другое дело. Ключевое слово: простых.

Ну, вот теперь, я думаю, взаимная простота сомножителей пригодится.

Может быть скажете откуда она берется?
Я много над этой задачей думал...
Максимум знаю расширенный алгоритм Евклида для доказательства взаимной простоты, но не знаю как его применить
Допустим, я применю и докажу.
Они взаимно просты, что дальше?
Они же могут быть вообще простыми , тогда взаимная простота ничего не дает, просто произведение $n$ простых, например

[nnosipov]

vatrushka в сообщении #1449859 писал(а):

Они взаимно просты, что дальше?

Да, похоже, здесь не так все очевидно. Проблема в том, что второй сомножитель может оказаться простым числом.

Надо еще подумать. Откуда задача?

[vatrushka]

https://docviewer.yandex.ru/view/321862 ... YwNDA5OCJ9

Вступительная в Computer Science Center
У меня была в прошлом году на экзамене
Честно говоря я уже довольно давно над ней думаю, но что то ничего не придумаю))

[tolstopuz]

Разложите на множители численно при $n=2$ и попробуйте подобрать общую формулу.