3^n+4^n

[nnosipov]

zykov в сообщении #1546509 писал(а):

Тут важно не то что $x^d \equiv 1$, а то что $\gcd{(a,b)} > 1$.

Ну, Вы прям мне глаза открыли. А я-то за 20 лет не удосужился узнать, что здесь важно, а что нет. Может, Вы просто не поняли, что я имел в виду?

zykov в сообщении #1546509 писал(а):

Т.е. более фундаментальное соображение тут то, что если $P_q(x)$ - порядок числа $x$ по модулю $q$
(наименьшая степень числа $x$ эквивалентная 1 по модулю $q$), то любая другая степень этого числа эквивалентная 1 будет кратна этому порядку.

А это уже следующее соображение --- понятие порядка элемента группы.

[zykov]

lel0lel в сообщении #1546511 писал(а):

Вообще по модулю два про порядок говорить не нужно, а по модулю семь порядок равен $2$.

По модулю два вообще нет $3/4$, т.к. $4$ необратимо. Но есть $4/3$. Здесь оно не важно, но это я к тому, что общий случай $a^n+b^n$ тоже работает.
Там на самом деле нужно не $4$ обращать, а $-4$.
По модулю 7 будет $-4 \equiv 3 \equiv 5^{-1}$ и соответственно $\frac{3}{-4} \equiv 1 \pmod 7$. Порядок равен 1.

[lel0lel]

zykov в сообщении #1546517 писал(а):

Там на самом деле нужно не $4$ обращать, а $-4$.

Но в сообщении у Вас написано про $3/4$. Впрочем, я понял о чём речь.

[maxal]

Процитирую свой ответ из http://math.hashcode.ru/answer_link/242932/

Другими словами, это нечетные $n$ удовлетворяющие сравнению

$$\left(-\frac{3}{4}\right)^n\equiv 1\pmod{n}.$$

Отсюда следует характеризация: $n$ является решением если и только если для всякого простого $p\mid n$ мультипликативный порядок $\mathrm{ord}_p(-3/4)\mid n$.

В частности, имеем, что для всякого простого $p\mid n$ все числа $p^k n\ (k\geq0)$ также являются решениями. ("накачка")

Заметив, что $\mathrm{ord}_p(-3/4)$ всегда делит $p-1$, нетрудно получить:

• если $p$ - минимальный простой делитель $n$, то мы с необходимостью имеем $\mathrm{ord}_p(-3/4)=1$, т.е. $p=7$.
• для всякого простого $p\mid n$ мультипликативный порядок $\mathrm{ord}_p(-3/4)$ делит произведение всех простых делителей (с учетом кратности) $n$ меньших $p$.

Таким образом, все решения (коих бесконечно много) можно получить из $n=1$ итеративно через (i) накачку; (ii) умножая решение $n$ на простой делитель числа $3^n+4^n$ не делящий $n$.

Искомые $n$ образуют последовательность A045584.

Можно также итеративно построить последовательность $P$ всех простых делителей искомых $n$: простое $p\in P$ если и только если все простые делители $\mathrm{ord}_p(-3/4)$ (которые меньше $p$) принадлежат $P$. Вот несколько начальных членов $P$:

$$7, 379, 14407, 689431, 4235659, 41647747, 137534083, 239900179, 242121643, \dots$$

Скоро появится в OEIS как последовательность A354026.