Fibonacci(n) modulo sequence.pdf Пусть F(n) обозначает n-е число Фибоначчи. Последовательность F(n) mod n (остаток от деления F(n) на n) показывает замечательно сложное поведение. На рис. 1 изображен график первых двухсот чисел этой последовательности. Стивен Волфрам [1] полагает, что возможно провести полный анализ поведения этой последовательности, например представив значение F(n) mod n в терминах стандартных теоретико-числовых функций от n, описать ее поведение простой примитивной рекурсией. Последовательность F(n) mod n представлена в on-line-энциклопедии Слоана последовательностью целых чисел [2], но там отсутствует анализ ее поведения. Автор исследует подпоследовательности вида F(qxp) mod qxp, где q - фиксированное натуральное число, a p пробегает простые числа. С помощью системы Mathematica вычисляются начальные отрезки подпоследовательностей, высказываются гипотезы, проводятся эксперименты для проверки. Доказаны достаточные условия на q, при которых значения последовательности F(qxp) mod qxp лежат только на двух прямых. В частности, первые 13 значений q суть 1, 2, 5, 10, 12, 24, 25, 36, 48, 50, 60, 72, 96. Когда в последовательности F(n) mod n встречаются нули? Перечислим известные факты. 1. Числа F(5k) mod 5k равны нулю для натурального k [3]. 2. Числа F(4x3k) mod 4x3k равны нулю для любого положительного целого k [4]. Но не только для n = 5k или n = 4x3k числа F(n) mod n равны 0. Были рассмотрены первые 250 тысяч чисел Фибоначчи. Отметим, что F(250 000) = 363561170109395618264261641757984 785699110243516470957309231046875. Пусть R обозначает множество {F(n) | n < 250 000, F(n) mod n = 0}. Оказывается, это множество состоит из 1406 чисел. Чисел вида F(5k) только восемь, n = 1, 5, 25, 125, 625, 3125, 15625, 78125. За исключением этих восьми чисел и числа F(52x3001) все остальные числа в R имеют вид F(12k). Чисел вида F(4x3k) только десять, n = 12, 36, 108, 324, 972, 2916, 8748, 26244, 78732, 236196. Три числа F(24), F(36) и F(60) из R имеют вид F(12p), где p - простое число. Остальные числа из R имеют вид F(12k), где k - составное число. Но обратное неверно. Среди первых 250 000 чисел Фибоначчи имеется 17094 числа, которые не принадлежат R, хотя номера их имеют вид 12k и k - составное. Первые три таких числа F(12x21), F(12x22) и F(12x26). Подпоследовательность F(p) mod p, p - простое Рассмотрим числа Фибоначчи с номерами, которые являются простыми числами. Отложим на оси абсцисс первые 200 простых чисел P(n) (n = 1, 2, ..., 200), а на оси ординат соответствующие значения F(P(n)) mod P(n). График полученных точек (P(n), F(P(n)) mod P(n)) изображен на рис. 2. F(P(n)) mod P(n) 1200 1000 800 600 400 200 200 400 600 800 1000 P(n) Изучение графика приводит к предположению, что F(p) mod p может быть равно только 1 или p - 1. Более детальный анализ с помощью системы Mathema-tica приводит к теореме. Теорема 1. a) Если простое p имеет вид 5t ± 1, то F(p) modp = 1. b) Если простое p имеет вид 5t ± 2, то F(p) modp = p - 1. Для доказательство теоремы нам потребуется лемма. Лемма 1 [5, с. 53-54]. a) Если простоеp имеет вид 5t ± 1, тоp делит 5(p-1)/2 -1. b) Если простоеp имеет вид 5t ± 2, тоp делит 5(p-1)/2 +1. Доказательство теоремы 1. Если p = 2, то F(p) = F(2) = 1 = -1 (mod 2). Поэтому в дальнейшем предполагаем, что p нечетно. По формуле Бине имеем F(p) = ^((^' - ') = = i C ((^)к - (-1)к (^)) = к=0 = ii i (2Cp ((^5)к) = 2 к=1, к нечетно =d-г i (Cp ((Т5)к-1) = 2 к=1, к нечетно ZF Ск 5(к-1)/2 = 2p 2 к=1, к нечетно ^ ^^(C-p + Сър 5 + С5р 52 +... + Сp - 25( p-3)/2 + СР 5( p-1)/2). Получаем 2p-1F (n) = С1р + 5 + С5p 52 +... + Сp-25( p-3)/2 + 5( p-1)/2. Так как cp = p Hp - к)! и, если 0 < к < p, то p в числителе С^ не сокращается. Поэтому все биномиальные коэффициенты в правой части, за исключением последнего, делятся на p, а Cpp = 1. Отсюда имеем 2p-1 F(p) = 5(p-1)/2 (mod p). По малой теореме Ферма 2p-1 = 1 (mod p). Поэтому, используя лемму 1, получаем утверждение теоремы. ■ Подпоследовательности F(qxp) mod qxp, p - простое Будем изучать подпоследовательности F(qxp) mod qxp, где q - фиксированное натуральное число, a p пробегает простые числа. Меняя q, имеем разное поведение подпоследовательностей. На рис. 3 - 8 видим типичные ситуации для некоторых небольших q. На оси абцисс размещаем числа qxP(n) (P(n) - n-е простое число), а на оси ординат соответствующие значения F(P(n)) mod P(n). F(2P(n)) mod 2P(n) 15 000 10 000 5000 15 000 2P(n) 0 5000 10 000 Рис. 3. График последовательности 2P(n) ^ F(2P(n)) mod 2P(n) F(3P(n)) mod 3P(n) 20 000 5000 10 000 15 000 20 000 Рис. 4. График последовательности 3P(n) ^ F(3P(n)) mod 3P(n) 0 3P(n) F(13P(n)) mod 13P(n) 100000 /> j »* 20 000 40000 60000 80000 100000 13P(n) F(17P(n)) mod 17P(n) 120000 100000 80 000 60 000 40 000 20 000 F(24P(n)) mod 24P(n) 140000 120000 100000 80 000 60 000 40 000 20 000 * >» \ 0 20 000 40 000 60 000 80 000 100 000 120 000 17P(n) Рис. 6. График последовательности 17P(n) ^ F(17P(n)) mod 17P(n) 150 000 24P(n) 50 000 0 100000 Рис. 7. График последовательности 24P(n) ^ F(24P(n)) mod 24P(n) F(25P(n)) mod 25P(n) 120000 100 000 80 000 60 000 40 000 20 000 25P(n) 0 50 000 100000 150000 На рис. 3, 7 и 8 значения (qxp, F(qxp) mod qxp) находятся на двух прямых, начиная с некоторого qxp0. Такие случаи изучены. Для n = 3p и n = 4p высказаны только гипотезы без доказательств. Ситуации, в которых поведение подпоследовательности F(qxp) mod qxp описывается двумя прямыми, первоначально изучались по отдельности для разных значений q. Затем полученные результаты были обобщены. Мы же сейчас начнем с доказательства общих результатов, а потом приведем следствия. Теорема 2. Пусть q - такое натуральное число, что выполнено условие Vp > max(5, F(q)) ^ F(qxp) = ± F(q) mod q. (1) (Сравнение в (1) выполнено одновременно как для положительных, так и для отрицательных значений F(q).) Тогда a) Если простое p имеет вид 5t ± 1, то F(qxp) mod qxp = F(q). b) Если простое p имеет вид 5t ± 2, то F(qxp) mod qxp = qxp - F(q). Для доказательства теоремы 2 нам потребуется две леммы. Лемма 2 (теорема Десмонда). Пусть p - простое число. Тогда для любого натурального n имеем F(pxn) = F(n) F(p) mod p. Оригинал изложен в [6]. Доступное доказательство см. в [3]. Лемма 3. Если сравнение a = b имеет место по нескольким разным модулям, то оно имеет место и по модулю, равному наименьшему общему кратному этих модулей. Доказательство. Если a = b (mod m) и a = b (mod n), то a - b делится на m и n и значит, что a - b делится на наименьшее общее кратное m и n. Доказательство теоремы 2. Теорема Десмонда дает F(qxp) = F(q) F(p) mod p. Поэтому по теореме 1: a1) Если простое p имеет вид 5t ±1, то F(qxp) = F(q) mod p. b 1) Если простое p имеет вид 5t ±2, то F(qxp) = - F(q) mod p. Если p > max(5, F(q)), то по условию (1) имеем a2) Если простое p имеет вид 5t ±1, то F(qxp) = F(q) mod q. b2) Если простое p имеет вид 5t ±2, то F(qxp) = - F(q) mod q. Так как p - простое и p > q, то наименьшее общее кратное p и q равно qp. Поэтому по лемме 3 имеем a3) Если простое p имеет вид 5t ±1, то F(qxp) = F(q) mod qxp. b3) Если простое p имеет вид 5t ±2, то F(qxp) = - F(q) mod qxp. Следовательно, для любого p > max(5, F(q)) выполнено утверждение теоремы. ■ Чтобы получить следствие из теоремы, нам необходима следующая лемма. Лемма 4. [5] Если n > 2, то F(m) делится на F(n) тогда и только тогда, когда m делится на n. Следствие 1. Пусть F(q) mod q = 0. Тогда для каждого p > max(5, F(q)) имеем a) Если простое p имеет вид 5t ± 1, то F(qxp) mod qxp = F(q). b) Если простое p имеет вид 5t ± 2, то F(qxp) mod qxp = qxp - F(q). Доказательство. Так как q делит ± F(q) и, по лемме 4, F(q) делит F(qx p), то F(qxp) = ± F(q) mod q. Получили условие (1). ■ Как мы знаем из введения, среди первых 250 000 значений q условие следствия 1 выполнено для 1406 значений q. Приведем несколько первых пар таких значений (q, F(q)); вторая компонента пары ограничивает снизу начальное значение p, начиная с которого поведение последовательности F(qxp) mod qxp описывается двумя прямыми. Первые значения q из следствия 1 q F(q) 5 5 12 144 24 46368 25 75025 36 14930352 48 4807526976 60 1548008755920 72 498454011879264 96 51680708854858323072 108 16641027750620563662096 Следствие 2. Пусть q = 2t, причем t не делится на 3 и t - делитель F(q). Тогда для каждого p > max(5, F(q)) имеем a) Если простое p имеет вид 5t ± 1, то F(qxp) mod qxp = F(q). b) Если простое p имеет вид 5t ± 2, то F(qxp) mod qxp = qxp - F(q). Доказательство. Покажем, что F(q) нечетно. Действительно, если 2 = F(3) делит F(2t), то, по лемме 4, имеем 3 - делитель t, что невозможно. Следовательно, F(q) = ± t (mod q). Так как p - простое и p > q, то pq не делится на 3. По лемме 4, F(qp) нечетно, но F(qp) делится на F(q). Отсюда следует, что F(qp) делится на t. Поэтому получаем F(qp) = ±t (mod q). Так как F(q) = ±t (mod q) и F(qp) = ±t (mod q), то F(qxp) = ± F(q) (mod q). Получили условие (1). ■ Первые шесть значений q, для которых выполнено условие следствия 2, есть 2, 10, 50, 110, 250 и 550. Предположения без доказательств Теорема 2 вместе со следствиями дает достаточные условия того, когда поведение подпоследовательностей F(qxp) mod qxp описывается двумя прямыми. В более сложных ситуациях (например, рис. 4 - рис. 6) удалось сформулировать только гипотезы, и то только в двух простейших случаях. Рис. 9 показывает поведение последовательности F(4p) mod 4p. То, что точки (4p, F(4p) mod 4p) последовательности F(4p) mod 4p располагаются на четырех прямых обнаружено с помощью системы Mathematica. И с помощью Mathematica были высказаны гипотезы (проверены для первой тысячи простых чисел). Возможно, для всех простых чисел справедливы следующие утверждения: Гипотеза 1. Если p = 1 или p = 19 по модулю 15, то F(4p) mod 4p = 3. Если p = 7 или p = 13 по модулю 15, то F(4p) mod 4p = 2p - 3. Если p = 2 или p = 8 по модулю 15, то F(4p) mod 4p = 4p - 3. Если p = 11 или p = 14 по модулю 15, то F(4p) mod 4p = 2p + 3. Гипотеза 2. Если p = 1 или p = 19 по модулю 30, то F(4p) mod 4p = 3. Если p = 7 или p = 13 по модулю 30, то F(4p) mod 4p = 2p - 3. Если p = 17 или p = 23 по модулю 30, то F(4p) mod 4p = 4p - 3. Если p = 11 или p = 29 по модулю 30, то F(4p) mod 4p = 2p + 3. Поиск подходящего модуля m осуществлялся среди тех т, у которых значение функции Эйлера ф(т) равно 4 или 8. Для m < 10 000 только два значения 15 и 30 оказались подходящими. Изучалось также поведение последовательности F(3p) mod 3p (см. рис. 10). То, что точки (3p, F(3p) mod 3p) последовательности F(3p) mod 3p располагаются на шести прямых, обнаружено с помощью системы Mathematica (проверено для первой тысячи простых чисел). Попытки сделать и в этом случае похожие предположения, как и в случае q = 4, оказались безуспешны. Поскольку прямых шесть, то подходящий модуль т отыскивался среди тех т, для которых функция Эйлера ф(т) была бы кратна 6, точнее, ф(т) должно быть равно 6, 12, 18 или 24. Были просмотрены все m < 10000, но подходящий модуль m не найден.

Скачать электронную версию публикации