Делимость Фибоначчи

[Andrey A]

Из Воробьева помню $p \mid F_{p_{\pm 1}$} (там зависимость по $\mod 5$), а вот делимость на степень простого воде бы не рассматривалась, и кажется было на форуме, но где? Второй вопрос: пусть $m$ - нечетное составное, и $x$ - наименьшее из таких, что $F_x\vdots \ m$ (аналог дискретного логарифма). Какие выводы можно сделать о делимости $m$, не прибегая по возможности к перебору и факторизации $x$? Или прибегая по минимуму. Спасибо.

[Sonic86]

Andrey A в сообщении #1335397 писал(а):

Из Воробьева помню $p \mid F_{p_{\pm 1}}$ (там зависимость по $\mod 5$), а вот делимость на степень простого воде бы не рассматривалась, и кажется было на форуме, но где?

Все должно быть точно так же. Есть формула Бине, из нее числа Фибоначчи выражаются как сумма двух сопряженных экспонент от $\frac{1\pm\sqrt{5}}{2}$. Когда мы переходим к вычетам по модулю $p^n$, элемент $\sqrt{5}\in\mathbb{F}_p \Leftrightarrow p\equiv \pm 1\pmod{5}$. Дальше если $\alpha\in \mathbb{F}_p$, то по теореме Эйлера порядок его $\alpha^{p^{n-1}(p-1)}\equiv 1\pmod {p^n}$. А если $\alpha\not\in \mathbb{F}_p$, то по модулю $p$ порядок уже равен $p^2-1$ - мощности мультипликативной группы конечного поля $\mathbb{F}^{\times}_p[\sqrt{5}]$. И потом от множителя $p-1$ избавляются (уже забыл как) - остается порядок $p+1$. И теперь надо скрестить ежа с ужом - рассмотреть $\mathbb{Z}/(p^n\mathbb{Z})[\sqrt{5}]$ и попытаться выполнить рассуждение по аналогии.
Полностью написать и проверить не могу - времени нет.

[Andrey A]

В конце концов первый вопрос интересует скорее в свете второго. Т.е. если $m$ в каноническом разложении содержит степени $>1$, как это может помочь/помешать сделать выводы из $x$ о делимости $m$.

[Sonic86]

Andrey A в сообщении #1335397 писал(а):

Из Воробьева помню $p \mid F_{p_{\pm 1}$} (там зависимость по $\mod 5$), а вот делимость на степень простого воде бы не рассматривалась

А все просто:
$F(n):=F_n$
$p\mid F\left(p-\left(\frac{5}{p}\right)\right)$
$F(n)=\frac{\varphi^n-\bar\varphi^n}{\varphi-\bar\varphi}, \varphi=\frac{1+\sqrt{5}}{2}$
$F(n)\equiv 0\pmod m \Leftrightarrow (\varphi/\bar\varphi)^n\equiv 1\pmod m$
$\alpha := \varphi/\bar\varphi = \frac{1+\sqrt{5}}{1-\sqrt{5}}$
Т.е. делимость $m\mid F(n)$ прямо равносильна поиску порядка $\alpha$ в конечных полях.
Т.к. $\alpha^{\left(p-\left(\frac{5}{p}\right)\right)}}\equiv 1\pmod p$, то
$\alpha^{\left(p-\left(\frac{5}{p}\right)\right)}}\equiv 1+(a+b\sqrt{5})p\pmod {p^2} \Rightarrow$
$\alpha^{p\left(p-\left(\frac{5}{p}\right)\right)}}\equiv 1\pmod {p^2} \Rightarrow$
$\alpha^{p^2\left(p-\left(\frac{5}{p}\right)\right)}}\equiv 1\pmod {p^3} \Rightarrow...$
$\alpha^{p^{k-1}\left(p-\left(\frac{5}{p}\right)\right)}}\equiv 1\pmod {p^k}$
$p^k\mid F_{p^{k-1}\left(p-\left(\frac{5}{p}\right)\right)}$
Только для $p=5$ я в этом не уверен
Но это конечно не минимальный индекс. Например отсюда только $13\mid F_{14}$, но уже $13\mid F_{7}$.
Минимальный индекс числа Фибоначчи, кратного хотя бы степени простого, прямо выражается через порядок $\alpha$ в конечных полях.

Andrey A в сообщении #1335508 писал(а):

В конце концов первый вопрос интересует скорее в свете второго.

Я сейчас тупой и писать буду тривиально, медленно и долго. Увы, прошу простить. Сразу рассмотреть в свете второго - это теперь дорогая для меня операция.

Andrey A в сообщении #1335397 писал(а):

Какие выводы можно сделать о делимости $m$, не прибегая по возможности к перебору и факторизации $x$?

Из полученной связи получается скорее всего, что без факторизации никак. Подумаю...

[Andrey A]

Sonic86 в сообщении #1336034 писал(а):

... скорее всего, что без факторизации никак.

Да, похоже на то. Это касается и дискретного логарифма. Собственно, и факторизация $x$ не всегда результативна. Поменяем обозначения: $f(m)$ - индекс наименьшего Фибоначчи, кратного $m$. Такой пример: $m=5777=53\cdot 109.\ \ f(53)=f(109)=f(5777)=27.$ Ни на $F_3$, ни на$F_9$ не делится, однако же $5777 \equiv -1 \mod 27.$ Вот и квазипростое. Тут надо подумать. Со степенями более-менее понятно, здорово Вы с ними разобрались, спасибо. Самое трудное оказалась пятерка! Страшнее кошки зверя нет:) В параллельной теме описывается алгоритм вычисления $f(m)$ (там это называется $q_m$, надо бы поменять терминологию). Факторизовать $f(m)$ можно попробовать через последовательность $f(m), f(f(m)),f(f(f(m))),$ и т.д. Если бы всё-таки захотелось. Оказывается $f(5^n)=5^n$ и $f(12\cdot 5^n)=12\cdot 5^n$, причем первое зациклено само на себя, ко второму приходит последовательность от любого $m\neq 5^n$, и очень быстро. Просто в качестве наблюдения, об остальном пока рано.

[Andrey A]

Andrey A в сообщении #1336091 писал(а):

... и очень быстро.

Длинненькая попалась: $f(2333)=389,f(389)=97,... 49,56,24,12,f(12)=12.$ Если делить по дороге на максимальную степень двойки и брать функцию от нечетных, то еще быстрее. Тогда конечный пункт -- степень пятерки.