2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Делимость Фибоначчи
Сообщение29.08.2018, 21:42 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Делимость Фибоначчи
Сообщение30.08.2018, 08:49 
Заслуженный участник


08/04/08
8520
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}]$ и попытаться выполнить рассуждение по аналогии.
Полностью написать и проверить не могу - времени нет.

 Профиль  
                  
 
 Re: Делимость Фибоначчи
Сообщение30.08.2018, 11:08 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Делимость Фибоначчи
Сообщение02.09.2018, 11:34 
Заслуженный участник


08/04/08
8520
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$?
Из полученной связи получается скорее всего, что без факторизации никак. Подумаю...

 Профиль  
                  
 
 Re: Делимость Фибоначчи
Сообщение02.09.2018, 17:33 
Заслуженный участник
Аватара пользователя


21/11/12
1406
Санкт-Петербург
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$, и очень быстро. Просто в качестве наблюдения, об остальном пока рано.

 Профиль  
                  
 
 Re: Делимость Фибоначчи
Сообщение03.09.2018, 11:28 
Заслуженный участник
Аватара пользователя


21/11/12
1406
Санкт-Петербург
Andrey A в сообщении #1336091 писал(а):
... и очень быстро.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group