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

[nnosipov]

Да уж, хитро. Где-то я подобный фокус (с числами Ферма, кажется; на какой-то украинской олимпиаде было) уже видел.

Upd. Вот здесь (см. решение задачи 10): https://dxdy.ru/topic89236.html.

[vatrushka]

$703 = 19 \cdot 37$
К чему меня это должно натолкнуть ?

[nnosipov]

vatrushka
Соотнесите множители с числом $3^3=27$.

[vatrushka]

$(3^3+ 3^2 + 1) \cdot( 3^3 - 3^2 - 1)$

[nnosipov]

Ну вот, только скобки расставьте, а то непонятно. И, конечно, в общем виде напишите.

[venco]

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

$(3^3+ 3^2 + 1) \cdot( 3^3 - 3^2 - 1)$

$(3^3+ 3^2 + 1) \cdot( 3^3 - 3^2 + 1)$

[vatrushka]

В общем, всем спасибо, я понял
${(3^{3^n})}^2 - 3^{3^n} + 1 = (3^{3^n} + 3^{\frac{3^n+1}{2}} + 1) \product (3^{3^n} - 3^{\frac{3^n+1}{2}} + 1) $

[Someone]

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

Может быть скажете откуда она берется?

Вопрос о взаимной простоте сомножителей в произведении

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

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

$$a^3+1=(a+1)(a^2-a+1)=(a+1)((a+1)^2-3a)$$

Числа $a$ и $a+1$ взаимно простые. Поэтому, если $a+1$ делится на $3$, то $\mathop{\mathrm{\text{НОД}}}(a+1,a^2-a+1)=3$, если же $a+1$ не делится на $3$, то $\mathop{\mathrm{\text{НОД}}}(a+1,a^2-a+1)=1$. У нас $a=3^{3^{n-1}}$, и при $n>0$ число $a+1$ на $3$ не делится.

Если обозначить

$$A_n=3^{3^n}+1,$$

то приведённое выше разложение при $n>0$ можно записать в виде

$$A_n=A_{n-1}\left(\left(3^{3^{n-1}}\right)^2-3^{3^{n-1}}+1\right).$$

Отсюда можно вывести, что все числа вида $\left(3^{3^{n-1}}\right)^2-3^{3^{n-1}}+1$ при разных $n>0$ попарно взаимно просты.
Кроме того, множители в разложении

$$\left(3^{3^{n-1}}\right)^2-3^{3^{n-1}}+1=\left(3^{3^{n-1}}-3^{\frac 12(3^{n-1}+1)}+1\right)\left(3^{3^{n-1}}+3^{\frac 12(3^{n-1}+1)}+1\right)$$

тоже взаимно простые, так как они не делятся ни на $2$, ни на $3$, а их разность равна $2\cdot 3^{\frac 12(3^{n-1}+1)}$.