Вычислить НОД разностей башен

[Руст]

Пусть

$$f(n)=n^{n^{n^n}}-n^{n^n}.$$

Вычислить наибольший общий делитель всех f(n) при n>2: НОД(f(3),f(4),f(5),...)=?

[Юстас]

Докажем чуть более общее утверждение.
Пусть $f_0(n)=1, f_k(n)=n^{f_{k-1}(n)}; g_{k+1}(n)=f_{k+1}(n)-f_k(n)$. Докажем, что для любого простого p>2 для любого k существует N: $g_k(N)$ не делится на p. Проведем индукцию по k: k=1 - очевидно.
Докажем $k\rightarrow k+1$. По предположению индукции, $\exists \beta: g_k(\beta)$ не делится на p-1(на какой-то из его простых делителей). Заметим далее, что

$$g_{k+1}(n)=f_k(n)(n^{g_k(n)}-1)$$

. Положим $N=\alpha(p-1)+\beta=\alpha\cdot p +\beta - \alpha$. Варьируя $\alpha$, можно сделать остаток от деления N на p любым. Пусть $q:=g_k(\beta) (mod (p-1))$; $s:=(\beta-\alpha)(mod (p)), s\ne 1$. Тогда s можно выбрать так, чтобы $s^q-1$ не делилось на p, что и докажет $g_k(N)$ не делится на p. Действительно, если $\forall s$ $s^q-1$ делится на p, то получим, что сравнение $x^{q-1}+x^{q-2}+\dots+1\equiv 0(mod p)$ степени не выше p-3 имеет p-2 различных решения, чего быть не может. Итак, искомый НОД равен $2^i$.

[Руст]

Вы и сами выделили проосто число 2 в особую категорию. На самом деле НОД делится на достаточную степень 2 (ни на 4 ни на 8, а больше 100). Таким образом, получаем, что в следующем шаге появляется делимость на 3 (p-1=2 - исключительное), даже на некоторую степень для окончательного числа. Следовательно в следующем шаге появляются и простые делители, для которых разложение на простые состоят из степени двойки и тройки, не превосходящих некоторого числа. Если этот процесс продолжать достаточно долго (что вы хотели под общим утверждением), то появиться делимость НОД на любое наперёд заданное простое число. Но здесь этот процесс обрывается на малом шаге, что позволяется вычислить все простые делители НОД и их степени, которыми они входят.

[Юстас]

Я немного исправил предыдущее сообщение, руководствуясь замечанием Руста. Осталось рассмотреть случай делимости на степени двойки и простые вида $4^k+1$, где $k\leqslant \frac i 2$, НОД делит $2^i$, остальное попадает под общий случай.

[Руст]

Почему такого вида. Я ведь говорил, что в четвёртом шаге появяться простые делители р, для которых р-1 равно $2^k*3$. В частности появляется делимость на 13.

[Юстас]

Согласен, я поторопился. Еще подумаю.

[evgeny]

А какой правильный ответ, $32640=2^7\cdot3\cdot5\cdot17$?

Для

$$ g(n) = n^{n^n} - n^n$$

ответ для $$\text{НОД}\limits_{i>2}\left(g(i)\right)$ будет $32=2^5$?

[Юстас]

Получается довольно нудное упражнение. Например для двойки ничего лучше составления такой таблицы:

$$\begin{array} {xxx} (2k+1)\equiv 1(mod{ 2})\\ (2k+1)^2\equiv 1(mod{ 4}) \\ \dots \\ (2k+1)^{64}\equiv 1 (mod{ 128}) \end{array} $$

и проверки придумать не удается. Для остальных чисел попроще, но все равно от большого перебора избавиться не удается.

[Руст]

На самом деле это не требует особого вычисления. Рассмотрим на какую степень двойки это число делится. Пусть n нечётное число, тогда $g_k(n)=f_{k-1}n*(n^{g_{k-1}(n)}-1)$. Соответственно минимум достигается, когда n=3 или 5 по модулю 8 и степень на 2 больше, чем у предыдущей (к-1)-ой функции. Учитывая, что для n=8n+3 степень двойки на которую делится первая функция равна 1, получаем, что $g_k(n)$ делится на степень $2^{2k-1}=2^7=128 (k=4)$ и это точная степень при n>2 (при n=2 это число меньше и поэтому потребовалось отделить). Когда число чётное больше 2, тем более имеется делимость на это число. Рассмотрим делимость на p. Опять надо рассмотрит отдельно случаи n делится на р и не делится. В первом случае, всегда (p>2) имеется делимость на большую степень. Поэтому, для нечётных простых р достаточно рассмотреть случай, когда n не делится на р. Если n образующая по модулю р, то $g_{k-1}(n)$ должно делиться на р-1, а для делимости на большую степень, на функцию Эйлера от этой степени. В случае, когда p=3 из того, что $g_2(n)$ всегда чётное получаем, что $g_3(n)$ всегда делится на 3, а значит $g_4(n)$ всегда делится на 9 и это максимальная степень.
Если обозначим через $t_k=t_k(n)=НОД(g_k(n),g_k(n+1),...)$, то получаем, что это число при n>=3 не зависит от n и $t_{k+1}$ вычисляется через него увеличением степеней простых делителей предыдущего на 1 (для простого р=2 на 2) и добавлением новых простых р, для которых $(p-1)|t_k.$ Учитывая, что $t_3=2^5*3$, получаем, что добавляются ещё новые простые 7,13,17,97. Таким образом $t_4=2^7*3^2*7*13*17*97.$

[maxal]

Руст писал(а):

Пусть

$$f(n)=n^{n^{n^n}}-n^{n^n}.$$

Вычислить наибольший общий делитель всех f(n) при n>2: НОД(f(3),f(4),f(5),...)=?

Рустем, а откуда эта задача?

На днях Михаил Бошерницан познакомил меня таким результатом (авторства M. Boshernitzan & J. Chaika):
Для любых натуральных чисел $a,b,c,d$ выполняется сравнение:

$$a^{b^{c^d}} \equiv a^{b^c}\pmod{2^{2^{2^2}}-2^{2^2}}$$

Такое же сравнение выполняется и для меньших башенок. А вот для больших это уже не так.

Предлагаю доказать в качестве задачи.

[Руст]

maxal писал(а):

Руст писал(а):

Пусть

$$f(n)=n^{n^{n^n}}-n^{n^n}.$$

Вычислить наибольший общий делитель всех f(n) при n>2: НОД(f(3),f(4),f(5),...)=?

Рустем, а откуда эта задача?

кажется эта задача была в Mathlinks, может и я внёс незначительное изменение.

Цитата:

На днях Михаил Бошерницан познакомил меня таким результатом (авторства M. Boshernitzan & J. Chaika):
Для любых натуральных чисел $a,b,c,d$ выполняется сравнение:

$$a^{b^{c^d}} \equiv a^{b^c}\pmod{2^{2^{2^2}}-2^{2^2}}$$

Такое же сравнение выполняется и для меньших башенок. А вот для больших это уже не так.

Предлагаю доказать в качестве задачи.

Это даже интереснее.
0. $a\equiv 1\mod 2-1$ очевидно.
1. $a^b\equiv a\mod 2^2-2$ так же очевидно.
2. Так как $2^{2^2}-2^2=12=2^2*3$ и используя $b^c\equiv b\mod 2$ - период для 3 получаем следующее $a^{b^c}\equiv a^b\mod 2^{2^2}-2^2$. На самом деле лучше отличать числа которые не меньше 3. Для этого класса верно более сильное сравнение $a^{b^c}\equiv a^b\mod 24$.
3. Здесь $2^{2^{2^2}}-2^{2^2}=2^{2^2}*(2^{2^{2^2}-2^2}-1)=2^4(2^{12}-1)=2^4*3^2*5*7*13.$
Учитывая, что $4|b^{c^d}-b^c$ и рассматривая чётный и нечётные случаи для а получаем, что $16|T(a,b,c,d)=a^{b^{c^d}}-a^{b^c}$. Для чисел больше или равно 3 имеется делимость на 32 и вообще для к уровня на $2^{k+2}$. Из того, что $12|b^{c^d}-b^c$ получаем, что $p^k|a^{b^{c^d}}-a^{b^c}$ для любого простого p, такого, что $p^{k-1}(p-1)|12$. А это как раз полученные числа.
Начиная со следующего уровня сильно растёт степень двойки а так же в разложении справа - разности башен из двоек появляются простые делители, для которых 2 не является образующей. По модулю таких простых сравнение не гарантировано.

[Sonic86]

Я про башенки немного не так решал.
По-моему вид модуля - просто совпадение.
Видимо, разность башенок высоты $n$ делится на $НОК(\phi^{(-n)} (1))$ просто переходом к показателям ($\phi$ - функция Эйлера). При этом получаются числа 1, 2, 6, потом наш модуль, а потом - очень огромное число, я его не напишу.
Ну и насчет двойки - как всегда отдельная история.

[Руст]

Если разница башни n+1 го порядка и n го порядка делится на $N_n$, то находится $N_{n+1}$ как произведение степеней простых чисел

$$N_{n+1}=\prod_{\phi (p^k)|N_n}p^k.$$

Только для р=2 степень можно увеличит на 1 при $n>2$, что связано с тем, что группа нечётных чисел по модулю $2^k$ не циклична при $k>2$ и есть $Z_2+Z_{2^{k-2}}$.
Поэтому, начиная с $N_0=1$ получаем $N_1=2$, $N_2=12$, $N_3=2^4*3^2*5*7*13$ дальше степени 2 увеличиваются на 2 (по сравнению с предыдущим, входящем в $N_n$), степеней нечётных простых на 1 и появляются новые простые множители p, для которых $p-1|N_n$.

[maxal]

Sonic86 писал(а):

По-моему вид модуля - просто совпадение.

Отнюдь. По сути задача эквивалентна нахождению НОД чисел вида

$$a^{b^{c^d}} - a^{b^c},$$

а число $2^{2^{2^2}}-2^{2^2}$ - это минимальное ненулевое такое число.

[Sonic86]

Да я понял.
Даже вполне естественно начинать искать НОД всех чисел начиная с первого, если последовательность растет.
Я имел ввиду, что действительно, если размер башни растет, то такой вид модуля не есть закономерность, не отражает ее. Наоборот, ее отражает, например, функция Эйлера.
Вот, к примеру, вопрос (видимо сложный): найти НОД энного модуля для данной задачи и разности башенок из двоек размером $n+1$ и $n$.