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 ] 

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



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

Сейчас этот форум просматривают: Padawan, Ёж


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

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