Бесконечно много

[rightways]

Найдите наименьшее натуральное число $a$ для которого существует бесконечно много натуральных $n$ для которых $n^3|a^n-1$.

[Sonic86]

Давайте хоть что-то напишем.
Ясно, что $a=1$ удовлетворяет условию задачи.
Будем предполагать, что $a>1$.

0) Мы знаем, что $(\forall n)n \nmid 2^n-1$, так что $a>2$

1) Для $a=3,n=2^k\Rightarrow n|3^n-1$ (доказывается по индукции по $k$)

2) Покажем, что для $a=3$ есть бесконечно много $n$ таких, что $n^2|3^n-1$.
Ясно, что $n=4$ удовлетворяет условию.
Далее по индукции: пусть $n$ такое, что $n^2|3^n-1$. Найдем простое $p$, взаимно простое с $n$ такое, что $(pn)^2|3^{pn}-1$
$(pn)^2|3^{pn}-1\Leftrightarrow\begin{cases}n^2|3^{pn}-1 \\ p^2|3^{pn}-1\end{cases}$
$n=4 \Rightarrow$ $p$ нечетно. Значит $n^2|3^n-1|3^{pn}-1$, 1-е условие системы выполняется, остается удовлетворить 2-е.
$3^n-1|3^{pn}-1$, будем подбирать $p:p|3^n-1, p\perp n$
Для этого нужно выделить из $3^n-1$ все делители числа $n$ и показать, что останется число большее 1.
$2|n$, $v_2(3^n-1)=v_2(n)+1$.
Далее, $n/4$ у нас по построению (по предположению индукции) будет свободно от квадратов. Т.е. если $q|n$, то $q||n$. Нетрудно видеть, что если $v_q(3^a-1)=1$, то $v_q(3^{aq^ks}-1)=k+1$ при $q\nmid s$. Т.е. если $q||n$, то $q^2||3^n-1=3^{q\frac{n}{q}-1}$.
Выделим все множители, останется $\frac{3^n-1}{(n/4)^2\cdot 2^3}=2\frac{3^n-1}{n^2}>2$ при $n>4$. И у этого числа наверняка найдется простой делитель, входящий в него в 1-й степени (это доказать не могу. А может и не надо? Может всю степень вытащить сразу?). Обозначим этот делитель $p$ - это тот самый искомый $p:p|3^n-1, p\perp n$
Наконец, если $p|3^n-1$, то $3^n=pt+1$ и тогда $p^2|3^{pn}-1=p^2t^2K+1-1$. 2-е условие удовлетворено.
Получаем, что существует бесконечное множество $n: n^2|3^n-1$ вида $4;4p_1;4p_1p_2;4p_1p_2p_3;...$. (например, $p_j=5;11;23;47;61;...$)

З.Ы. Текст невменяемый вышел завтра отредактирую.

[Sonic86]

(попытка №2, неудачная)

Исправляю пункт 2):
Обозначения:
$a\perp b$ означает $\gcd(a,b)=1$.
Для простого $p$ соотношение $p^k||A$ означает, что $v_p(A)=k$.
$a||b$ означает, что $a|b$ и $\frac{b}{a}\perp a$

2) Докажем по индукции, что существует бесконечно много $n: n^2||3^n-1$.
Будем искать $n$ в виде $p_0^{a_0}...p_s^{a_s}, a_j>0, p_0<...<p_s, $.
Базис: $n:=4$: $4^2|3^4-1=4^2\cdot 5$.
Шаг: пусть $n:n^2||a^n-1$. Построим $p,k:(np^k)^2||a^{np^k}-1, k>0,p>p_j, p\perp n$.
Поскольку $p^{2k}\perp n^2$, то

$$(np^k)^2|a^{np^k}-1\Leftrightarrow\begin{cases}n^2||3^{np^k}-1 \\ p^{2k}||a^{np^k}-1\end{cases}$$

$p$ нечетно $\Rightarrow a^n-1|a^{np^k}-1$, значит $n^2||a^n-1|a^{np^k}-1$. Покажем, что $n^2||a^{np^k}-1$. Последнее равносильно $(\forall j)p_j^{a_j}||a^{np^k}-1$. Так как $p>p_j,$ то $p^k \perp \varphi(p_j^{a_j})$, значит

$$p_j^{a_j}||a^{np^k}-1\Leftrightarrow \begin{cases} a^{np^k}\equiv 1\pmod{p_j^{a_j}} \\ a^{np^k}\not\equiv 1\pmod{p_j^{a_j+1}} \end{cases}\Leftrightarrow \begin{cases} a^{n}\equiv 1\pmod{p_j^{a_j}} \\ a^{n}\not\equiv 1\pmod{p_j^{a_j+1}} \end{cases}\Leftrightarrow p_j^{a_j}||a^n-1$$

Далее, несложно видеть, что $p^{2k}||a^{np^k}-1\Leftrightarrow p^k||a^n-1$. Действительно, пусть $p^r||a^n-1$, т.е. $a^n=1+Qp^r, p\nmid Q$, тогда по биному Ньютона $a^{np^k}=1+Q_1p^{r+k}, p\nmid Q_1$, так что $r+k=2k$, т.е. $p^k||a^n-1$. Т.е. нам нужно лишь подобрать $p^k$, удовлетворяюшего этому соотношению и предыдущим ограничениям $p\perp n,p>p_j$.
Разложим $a^n-1=TR$, где $T$ - максимальный делитель $a^n-1$, взаимно простой с $n$, а $R=\frac{a^n-1}{T}$. В силу способа построения $n$ $R=n^2$. Тогда $T=\frac{a^n-1}{n^2}>1$ при $n\geqslant 4$. Следовательно $(\exists p,k)p^k||T$, а поскольку $T\perp R$, то и $p\perp n^2$. Остается доказать, что $(\forall j)p>p_j$. Это можно доказать так:
$p^k||T\Rightarrow p^k||a^n-1\Rightarrow a^n\equiv 1\pmod{p}$
Пусть $\delta$ - показатель $a$ по модулю $p$: $a^{\delta}\equiv 1\pmod{p}$. Тогда $\delta | n$ и $\delta|\varphi(p)$, т.е. $\delta=p_0^{b_0}...p_s^{b_s}<p$, в частности $p_j<p$. здесь не доказано! возможно, вместо $p^k$ надо брать куски побольше - сразу $\frac{a^n-1}{n^2}$ и тогда м.б. получится. Попробую попозже.
В результате индукционный шаг типа выполнен, типа получаем бесконечно много искомых $n$ для $a=3$.

3) Скорее всего не существует $a>1$ такого, что множество $\{n: \ n^3|a^n-1\}$ бесконечно. Но доказать не могу - нет знаний о числе степеней в разложении числа $a^n-1$

[Sonic86]

Попытка №3, удачная.
Обозначения:
$a\perp b$ означает $\gcd(a,b)=1$.
$a||b$ означает, что $a|b$ и $\frac{b}{a}\perp a$.

2) Докажем по индукции, что существует бесконечно много $n: n^2||3^n-1$.
Будем искать $n$ в виде $p_0^{a_0}...p_s^{a_s}$.
Базис: $n:=4$: $4^2|3^4-1=4^2\cdot 5$.
Шаг: пусть $n:n^2||a^n-1$. Построим $q:(nq)^2||a^{nq}-1, q\perp n$.
Положим $q:=\frac{a^n-1}{n^2}$. Т.к. $n^2||a^n-1$, то $q||a^n-1$ и $q\perp n$.
Так как $q||a^n-1$, то $q^2||a^{nq}-1$.

(доказательство)

Здесь для доказательства придется обращаться к простым делителям:
$q||a^n-1\Leftrightarrow (\forall p^k)p^k||q\Rightarrow p^k||a^n-1$
$p^k||a^n-1\Rightarrow a^n=1+p^kQ,p\nmid Q\Rightarrow$ по биному Ньютона $a^{np^k}=1+p^{2k}Q_1,p\nmid Q_1\Rightarrow a^{nq}=1+p^{2k}Q_2, p\nmid Q_2$ $\Leftrightarrow p^{2k}||a^{nq}-1$
И обратно: из $(\forall p^k)p^k||q\Rightarrow p^{2k}||a^{nq}-1$ следует, что $q^2||a^{nq}-1$.

Получаем: $q^2||a^{nq}-1$, $n^2||a^n-1$, $n\perp q$. Рассуждая так же, как выше, получаем, что $n\perp q\Rightarrow n^2||a^{nq}-1$.
$n^2||a^{nq}-1$ и $q^2||a^{nq}-1$ и $n\perp q$ $\Rightarrow (nq)^2||a^{nq}-1$.

Просьба хоть как-нибудь проверить.

[Sonic86]

3.3) Докажем, что существует лишь конечное число $n:n^3|3^n-1$.
Ограничимся $n:n>1$.
Пусть $n$ произвольно, $p$ - минимальное простое, делящее $n$, $p^k||n, n=p^kq$, тогда $p^{3k}|3^{p^kq}-1$. Поскольку $p\perp q$ и все простые делители $q$ больше, чем $p$, то $\varphi(p^k)\perp q$, значит $p^{3k}|3^{p^kq}-1\Leftrightarrow p^{3k}|3^{p^k}-1\Rightarrow p=2$.
Значит $n=2m$, подставляем: $8m^3|3^{2m}-1$. Рассмотрим степени двойки обеих частей:
$v_2(8m^3)=3+3v_2(m)$, а $v_2(3^{2m}-1)=3+v_2(m)$, откуда $3+3v_2(m)\leqslant 3+v_2(m)$, т.е. $v_2(m)=0$, т.е. $m$ нечетно.
$m$ нечетно, значит $8m^3|3^{2m}-1\Leftrightarrow m^3|3^{2m}-1$.
Дальше рассуждаем аналогично: пусть $p$ - минимальный простой делитель $m$, $p$ нечетно, $p^k||m$, тогда $p^{3k}|3^{2m}-1$, откуда так же $p^{3k}|3^{2p^k}-1\Leftrightarrow p^{2k}|3^2-1$, что невозможно для нечетного $p$.

Остается рассмотреть случаи $a>3$.

(Оффтоп)

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

upd:
3.2k) Пусть $a$ четно, тогда $n$ нечетно.
Пусть $p_1$ - минимальный простой делитель $n$, $p_1^{k_1}||n, n=p_1^{k_1}n_1$. Тогда $n^3|a^n-1\Rightarrow p_1^{3k_1}|a^{n_1p_1^{k_1}}-1\Leftrightarrow p_1^{3k_1}|a^{p_1^{k_1}}-1\Leftrigtharrow p_1^{2k_1}|a-1$.
Выберем какие-нибудь $p_1,k_1$, если таковые существуют.
Продолжим рассуждать аналогично: пусть $p_2$ - минимальный простой делитель $n_1$, $p_2^{k_2}||n, n_1=p_2^{k_2}n_2. $
Тогда $n^3|a^n-1\Rightarrow p_2^{3k_2}|a^{n_2p_1^{k_1}p_2^{k_2}}-1\Leftrightarrow p_2^{3k_2}|a^{p_1^{k_1}p_2^{k_2}}-1\Leftrigtharrow p_2^{2k_2}|a^{p_1^{k_1}}-1$.
Получаем цепочку соотношений:
$p_1^{2k_1}|a-1$
$p_2^{2k_2}|a^{p_1^{k_1}}-1, p_2>p_1$
...
Для фиксированного четного $a$ с помощью этих соотношений можно быстро проверить, что $a$ не удовлетворяет условию.
Например, 1-му условию не удовлетворяют $a=2;4;6;8;12;14;16;18;20;22;24$, значит, они не являются решением. Вообще, если $a-1$ нечетно и свободно от квадратов, то оно не удовлетворяет условию.
Для $a=10, a-1=9=3^2, \Rightarrow a^3-1=3^3\cdot 37$ - нетривиальных новых степеней нет.
И т.д.
Для $a=26, a-1=5^2, \Rightarrow a^5-1=5^3\cdot 11 \cdot 8641$ - нетривиальных новых степеней нет.