Congruences of the Fibonacci numbers modulo a prime.pdf Почти все результаты, доказанные в этой статье, первоначально были обнаружены в рамках экспериментальной математики [1] с помощью системы Mathematica с языком программирования Wolfram [1, 2]. Эксперименты помогли сформулировать цепочки достоверных догадок, доказать которые оказалось уже нетрудно. Кроме того, Mathematica применялась для получения примеров, иллюстрирующих изложение. Через F(n) будем обозначать числа Фибоначчи. Следуя [3], считаем F(0) = 0, F(1) = 1, и для отрицательных индексов доопределяем числа Фибоначчи с помощью правила F(-n) = (-1)n-1F(n). (1) Это равенство остается в силе и когда n меняет свой знак. Теперь для любого целого n имеем F(n + 2) = F(n + 1) + F(n). Мы начинаем с известных фундаментальных фактов ([4, с. 78-79] или [2, с. 232]). В дальнейшем до конца статьи через р обозначаются положительные простые числа. Лемма 1. a) Если простое p имеет вид 5t ± 1, то F(p) = 1(modp). b) Если простое p имеет вид 5t ± 2, то F(p) = -1(modp). c) Если простоеp имеет вид 5t ± 1, то F(p - 1) = 0(modp). d) Если простое p имеет вид 5t ± 2, то F(p + 1) = 0(modp). Отсюда, используя определение чисел Фибоначчи, сразу следует, что e) Если простое p имеет вид 5t ± 1, то F(p + 1) = 1(mod p). f) Если простое p имеет вид 5t ± 2, то F(p - 1) = 1(modp). Теорема 1. Пусть простое p имеет вид 5t ± 1 и b - целое число. Тогда имеем F(p + b) = F(b + 1) (mod p). (2) Доказательство. Будем рассматривать два различных случая. 1. Случай p + b > 0. Будем использовать математическую индукцию по возрастанию b. Базис индукции составляют два сравнения для b = 0: F(p + 0) = F(0 + 1) х В.М. Зюзьков 16 х (modp) - это лемма 1(a); и для b = 1: F(p + 1) = F(1 + 1)(mod p) - это лемма 1(e). Докажем индуктивный переход. Пусть выполнено F(p + b) = F(b + 1) (mod p) и F(p + (b + 1)) = F((b + 1) + 1) (mod p). Почленно сложим эти сравнения, что дает F(p + b) + F(p + (b +1)) = F(b + 1) + F((b + 1) + 1) (mod p). Суммы последовательных чисел Фибоначчи в последнем сравнении дают необходимое заключение F(p + (b + 2)) = F((b + 2) + 1) (mod p). 2. Случай p+b < 0. Теперь b < 0 и математическая индукция будет по убыванию b. Базис индукции составляют два сравнения для b = 0: F(p + 0) = F(0 + 1)(mod p) -это лемма 1(a); и для b = -1: F(p - 1) = F(-1 + 1) (mod p) - это лемма 1(с). Докажем индуктивный переход. Пусть выполнены сравнения F(p + b) = F(b + 1) (mod p) и F(p + (b - 1)) = F((b - 1) + 1) (mod p) и почленно вычтем эти сравнения, что дает F(p + b) - F(p + (b - 1)) = F(b + 1) - F((b - 1) + 1) (modp). Разности последовательных чисел Фибоначчи в последнем сравнении дают необходимое заключение F(p + (b - 2)) = F((b - 2) + 1) (modp). Таким образом, сравнение (2) доказано. ■ Следствие 1. Пусть простое p имеет вид 5t ± 1 и b - целое число. Тогда имеем F(-p + b) = F(b - 1) (modp). (3) Доказательство. Имеем F(-p + b) = (-1)-p+b-1F(p - b) и, учитывая (1), (2) и нечетность p, получаем сравнение F(-p + b) = (-1)bF(1 - b) (mod p). Снова применяя (1), получаем (-1)bF(1 - b) = (-1)b(-1)1-b-1F(b - 1) = F(b - 1), что дает (3). ■ Сейчас исследуем, какое сравнение по модулю p выполнено для ap + b, где a -произвольное целое число. Несколько вычислений c небольшими a, b и p приводят к предположению, что F(ap + b) = F(a + b) (mod p). Проделаем более серьезную экспериментальную проверку этого предположения. Сначала создадим список ps простых чисел вида p = ±1 (mod 5) и не превосходящих простого числа с номером 200. I ps = Select[Prime[Range[200]], Mod[#, 5] = = 1 || Mod[#, 5] = = 4&]; Можно посмотреть на начало и конец этого списка, пропуская 76 чисел: Short[ps] {11, 19, 29, 31, 41, 59, 61, 71, 79, , 1061, 1069, 1091, 1109, 1129, 1151, 1171, 1181, 1201} Далее тысячу раз будем генерировать пары a и b в диапазоне от -50 до 50 включительно. И для каждой пары будем перебирать все простые числа p из списка ps и выдавать булевское значение, говорящее о делимости F(ap + b) - F(a + b) на p. Каждый раз берем конкатенацию этих значений. Все результаты тысячи конкатенаций собираем также в один список ss и делаем окончательную конкатенацию. ss = { }; Do[a = RandomInteger[{-50, 50}]; b = RandomInteger[{-50, 50}]; AppendTo[ss, And@@(Divisible[Fibonacci[a # + b] - Fibonacci[a + b], #]& /@ ps)],1000]; And @@ ss True Результат True говорит о том, что предположение оказалось верным для всей тысячи вариантов. Сравнения с числами Фибоначчи по простому модулю 17 Теорема 2. Пусть простое p имеет вид 5t ± 1 и a, b - целые числа. Тогда имеем F(a p + b) = F(a + b) (mod p). (4) Доказательство. Для a = 0 сравнение очевидно. Рассмотрим еще два случая. 1. a > 0. Доказательство будем проводить математической индукцией по возрастанию a. Базис индукции при а = 1 доказан в теореме 1. Для индуктивного шага предположим, что сравнение (4) выполнено для ap плюс любое целое число. Тогда F((a + 1)p + b) = F(ap + (p + b)) = F(a + (p + b)) (mod p). Далее имеем F(a + (p + b)) = F(p + (a + b)) = (по теореме 1) F(a + 1 + b) (mod p). Таким образом, доказано сравнение (4) для a + 1. 2. a < 0. Доказательство будем проводить математической индукцией, уменьшая a. Базис индукции при а = -1 доказан в следствии 1. Для индуктивного шага предположим, что сравнение (4) имеет место для ap плюс любое целое число. Тогда F((a - 1)p + b) = F(ap + (-p + b)) = F(a + (-p + b)) (mod p). Далее получаем F(a + (-p + b)) = F(-p + (a + b)) = (по следствию 1) F(a - 1 + b) (modp). Таким образом, доказано сравнение (4) для a - 1. ■ Теорема 3. Пусть простое p имеет вид 5t ± 1, к > 0 - натуральное число и целые числа ak, ak-1, ..., a2, ax, a0 - коэффициенты многочленаA(x). Тогда имеем F(A(p)) = F(ak + ak-x + ... + a2 + ax + a0) (modp). (5) Доказательство. Сначала докажем, что для целых чисел n > 1, a и b выполнено F(apn + b) = F(a + b) (mod p). (6) Будем проводить математическую индукцию по n. Базис индукции для n = 1 доказан в теореме 2. Пусть (6) выполнено для некоторого n. Докажем выполнимость (6) для n + 1. Имеем равенство F(apn+ + b) = F((apn)p +b) и снова в силу теоремы (2) получаем F((apn)p +b) = F(apn + b)(mod p). Используя индуктивное предположение, получаем требуемое сравнение F(apn+l + b) = F(a + b) (mod p). Для доказательства утверждения (5) обозначим для любого натурального т, к> т > 0, через Bm(x) многочлен с коэффициентами am, am-x, ..., a2, ax, a0. Имеем Bm(x) = ampm + Bm-1(x), и тогда из (6) следует, что F(Bm(p)) = F(ampm + + Bm-l(p)) = F(Bm-x(p) + am) (modp). Повторяя это преобразования до m = 1, получаем (5). Следствие 2. Пусть N - натуральное число, которое в p-ичной системе счисления имеет цифры ak, ak-1, ..., a2, ax, a0 Тогда F(N) = F(ak + ak-1 + ... + a2 + ax + a0)x x(mod p). Перейдем к рассмотрению свойств, аналогичных свойствам, описанным в теоремах 1-3, для нечетных простых чисел вида 5t ± 2. Формулировка следующей теоремы возникла после экспериментальной проверки для b е [-1000, 1000] и для всех простых чисел вида 5t ± 2 с порядковыми номерами, не превосходящими 1000. Теорема 4. Пусть простое p имеет вид 5t ± 2 и b - целое число. Тогда имеем F(p + b) = -F(b - 1) (modp). (7) Доказательство. Это доказательство аналогично доказательству теоремы 1. Рассмотрим два различных случая. 1. Случай p + b > 0. Будем использовать математическую индукцию по возрастанию b. Базис индукции составляют два сравнения для b = 0: F(p + 0) = = -F(0 - 1) (mod p) - это лемма 1(b); и для b = 1: F(p + 1) = -F(1 - 1)(mod p) -это лемма 1(d). Докажем индуктивный переход. Пусть выполнены сравнения В.М. Зюзьков 18 F(p + b) = -F(b - 1)(mod p) и F(p + (b + 1)) = -F((b + 1) - 1) (mod p), что после почленного сложения получаем F(p + b) + F(p + (b +1)) = -F(b - 1) - F((b + 1) - 1) (mod p). Суммы последовательных чисел Фибоначчи в последнем сравнении дают необходимое заключение F(p + (b + 2)) = -F((b + 2) - 1) (modp). 2. Случай p + b < 0. Теперь b < 0 и математическая индукция будет по убыванию b. Базис индукции составляют сравнения: для b = 0 имеем F(p + 0) = -F(0 - 1)х x(mod p) - это лемма 1(b); и для b = -1 имеем F(p - 1) = -F(-1 - 1) (mod p) -это лемма 1(f). Докажем индуктивный переход. Пусть выполнены сравнения F(p + b) = -F(b - 1) (mod p) и F(p + (b - 1)) = -F((b - 1) - 1) (mod p) и почленное сложение этих сравнений дает F(p + b) + F(p + (b - 1)) = -F(b - 1) - F((b - 1) - 1) (modp). Суммы последовательных чисел Фибоначчи в последнем сравнении дают необходимое заключение F(p + (b +1)) = -F(b) (mod p). Таким образом, сравнение (7) доказано. ■ Следствие 3. Пусть нечетное простое p имеет вид 5t ± 2 и b - целые числа. Тогда имеем F(-p + b) ^ -F(b + 1) (mod p). (8) Доказательство. Применяя (1), имеем F(-p + b) = (-1)-’+b-1F(p - b) = (-1)bF(p - b), учитывая нечетность p. Поэтому сравнение (7) дает F(-p + b) = (-1)b+1 F(-b - 1)x x(mod p). Наконец, снова применяя (1), получаем F(-p + b) = -F(b + 1) (mod p). ■ Сейчас исследуем, какое сравнение по модулю p выполнено для F(ap + b), где p - нечетное простое и имеет вид 5t ± 2, и a, b - целые числа. Эксперименты c различными числами a, b и p привели к предположению, что F(ap + b) = (-1)a х x F(b - a)(mod p). Была проделана ниже описанная проверка этого предположения в системе Mathematica. Создан список ps простых чисел вида p = ±2 (mod 5) и не превосходящих простого числа с номером 200. I ps = Select[Prime[Range[200]], Mod[#, 5] = = 2 || Mod[#, 5] = = 3&]; Можно посмотреть на начало и конец этого списка, пропуская 86 чисел: Short[ps] {3, 7, 13, 17, 23, 37, 43, 47, 53, , 1117, 1123, 1153, 1163, 1187, 1193, 1213, 1217, 1223} Далее тысячу раз генерируются пары случайных чисел a и b в диапазоне от -50 до 50 включительно. И для каждой пары перебираются все простые числа p из списка ps и выдаётся булевское значение, говорящее о делимости F(ap + b) -- (-1)aF(b - a) на p. Вычисляется конкатенация этих значений. Все результаты тысячи конкатенаций собираются также в один список ss и делается окончательная конкатенацию. ss = { }; Do[a = RandomInteger[{-50, 50}]; b = RandomInteger[{-50, 50}]; AppendTo[ss, And@@(Divisible[Fibonacci[a # + b] - (-1)“Fibonacci[b - a], #]& /@ ps)],1000]; And @@ ss True Результат True говорит о том, что предположение оказалось верным для всей тысячи вариантов. Догадываясь, какой вид имеет искомое сравнение, нетрудно провести доказательство. Сравнения с числами Фибоначчи по простому модулю 19 Теорема 5. Пусть нечетное простое p имеет вид 5t ± 2 и a Ф 0, b - целые числа. Тогда имеем F(ap + b) - (-1)aF(b - a) (mod p). (9) Доказательство. Если a = 0, то обе части в (9) совпадают. Сравнение (9) для случая a > 0 докажем методом математической индукции. Базис индукции при a = 1 выполнен по теореме 4. Пусть по индуктивному предположению сравнение (9) выполнено для a = n и для любого b. Тогда F((n + 1)p + b) = F(np + p + b) - - (-1)nF(p + b - n) (mod p) и по теореме 4 следует, что (-1)nF(p + b - n) - - (-1)n(-1)F(b - n - 1)(mod p). Правая часть последнего сравнения равна (-1)n+1F(b - (n + 1)), что доказывает индуктивный шаг. Теперь рассмотрим a < 0. С помощью (1) переходим к положительному множителю перед p: F(ap + b) = (-1)ap+b-1F(-ap - b) - (-1)ap+b~l(-1)~aF(-b + a) (mod p). В правой части сравнения снова применяем (1), получаем (-1)ap+b-1(-1)-a х x(-1)-b+a-1F(b - a) = (-1)apF(b - a) и имеем (-1)ap = (-1)a для нечетного p. На этом доказательство (9) заканчиваем. ■ Теорема 6. Пусть нечетное простое p имеет вид 5t ± 2, к > 0 - натуральное число и целые числа ak, ak-1, ..., a2, ab a0 - коэффициенты многочлена A(x). Тогда имеем к к F (A(p)) - (-1)rF (S )(mod p), где S = £ (-1)' at, R = X a. (10) i=0 i=0 Доказательство. Сначала докажем, что для целых чисел m > 0, a Ф 0 и b выполнено F(apm + b) - (-1)amF(b + (-1)ma) (mod p). (11) Базис математической индукции при m = 0 очевидно выполнен. Пусть по индуктивному предположению (11) выполнено для m = n для любого a и b. Тогда по теореме 5 имеем сравнение F(apn+l + b) = F((apn)p + b) - (-1)aF(b - apn) (mod p), так как четности чисел apn и a совпадают. Далее, применяя индуктивное предположение, получаем сравнение (-1)aF(b - apn) - (-1)a(-1)-anF(b + (-1)n(-a))(mod p). Но правая часть сравнения равна (-1)a(n+1)F(b - (-1)n+1), поскольку 1 - n и n + 1 имеют одинаковую четность. Что и доказывает индуктивный шаг. Для доказательства утверждения (10) обозначим для любого натурального m, с условием к > m > 0, через Bm(x) многочлен с коэффициентами am, am-1, ..., a2, ab a0. Имеем Bm(x) = ap + Bm-1(x) (12) и, таким образом, из (11) следует, что F(Bm (p)) = F(ampm + Bm_j(p)) - (-1)ammF(Bm_1 (p) + (-1)m )(mod p). Повторно применяя (12) и (11), получаем F(Bm (p)) - (-1)amm (-1)am-1(m-1)F(Bm_2 (p) + (-1)mam + (-1)m-1 am_1)(mod p). Этот процесс будем повторять, пока не дойдем до m = 1. Окончательно, получаем m m F(Bm (p)) - (-1)Rm F(Sm )(mod p), где Sm = X (-1)4, Rm = X Ц. i=0 i=0 При замене m на к имеем (10). ■ В.М. Зюзьков 20 Пример. Пусть A(x) = 6x4+16x3+13x2- 7x - 275. Тогда R = 6-4 + 16-3 + 13-2 -7 = 107, S = 6 - 16 + 13 + 7 - 275 = - 265. Возьмем p = 13. Вычислим значение многочлена A(p): A = 6хЛ4 + 16хл3 + 13хл2 - 7х - 275; A /. х ^ 13 208349 Оценим количество десятичных цифр в числе F(208349). Length[IntegerDigits[Fibonacci[208349]]] 43543 Значения левой и правой частей сравнения (10) совпали по модулю 13. I {Mod[Fibonacci[208349], 13], Mod[-Fibonacci[-265], 13]} I {1, 1} Сравнения (5) и (10) приводят к следствиям, связанным с понятием периода Пизано. Последовательность чисел Фибоначчи {F(n)} по модулю является периодической для любого модуля m и соответствующий период называется периодом Пизано и его длина обозначается как n(m) [5]. Например, для m = 5 в последовательности {F(n)} mod 5 повторяющейся подпоследовательностью является период Пизано {0, 2, 2, 4, 1, 0, 1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, 3, 2} и п(5) = 20. По определению периода Пизано для любого целого n и любого модуля m имеет место сравнение F(n) = F(n mod n(m)) (mod m), (13) где внутренний “mod” обозначает операцию нахождения остатка от целочисленного деления. Следствие 4. Пусть простое p имеет вид 5t ± 1, натуральное к > 0 и целые числа a0, а1, a2, ..., ак_ь ак образуют период Пизано длиной к + 1 для чисел Фибоначчи по модулю р. Положим s = а0 + аі+ а2 + ...+ ак-1 + ак и A(x) - многочлен степени к с коэффициентами а. Тогда имеет место сравнение F(s) = F(A(p) mod (к + 1))(modр). (14) Доказательство сразу следует из сравнений (5) и (13) при m = p и n = A(p). Следствие 5. Пусть нечетное простое p имеет вид 5t ± 2, к > 0 - натуральное число и целые числа а0, а!, а2, ..., ак-1, ак образуют период Пизано длиной к + 1 для чисел Фибоначчи по модулю p. Положим A (x) - многочлен степени к с коэффициентами а. Обозначим через S, R и е выражения S = X (-1) аг, R = X а и е = (-1)R. i=0 i=0 Тогда имеем е F(S) = F(A(p) mod (к + 1))(modp). (15) Доказательство сразу следует из сравнений (10) и (13) при m = p и n = A(p).
Зюзьков В.М. Эксперименты в теории чисел. Томск: Изд-во НТЛ, 2019. 348 с. URL: http://vital.lib.tsu.rU/vital/access/manager/Repository/vtls:000658998
Wolfram Mathematica. URL: http://www.wolfram.com/mathematica
Грэхем Р., Кнут Д., Поташник О. Конкретная математика. Основание информатики. 2-е изд., испр. М.: Мир; БИНОМ. Лаборатория знаний, 2006. 703 с.
Vajda S., Fibonacci & Lucas Numbers and the Golden Section: Theory and Applications, Ellis Horwood, Chichester, England, 1989. 190 p.
Weisstein Eric W. Wolfram MathWorld: Pisano Period. URL: https://mathworld.wolfram.com/ PisanoPeriod.html