Подільність елементів зворотних послідовностей
Нехай un – n-е число Фiбоначчi, p – просте число. Тодi, якщо 5-квадратичний лишок у полi лишкiв за модулем p, то un(p-1) ≡ 0(modp), якщо 5-квадратичний нелишок, то un(p+1) ≡ 0(modp). Дається узагальнення цього результату на довiльнi зворотнi послiдовностi другого порядку...
Збережено в:
| Дата: | 2012 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2012
|
| Назва видання: | Труды Института прикладной математики и механики |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/124125 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Подільність елементів зворотних послідовностей / А.Г. Матюхіна, Л.Л. Оридорога // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2012. — Т. 25. — С. 161-165. — Бібліогр.: 7 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-124125 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1241252017-09-21T03:03:04Z Подільність елементів зворотних послідовностей Матюхіна, А.Г. Оридорога, Л.Л. Нехай un – n-е число Фiбоначчi, p – просте число. Тодi, якщо 5-квадратичний лишок у полi лишкiв за модулем p, то un(p-1) ≡ 0(modp), якщо 5-квадратичний нелишок, то un(p+1) ≡ 0(modp). Дається узагальнення цього результату на довiльнi зворотнi послiдовностi другого порядку Пусть un – n-ое число Фибоначчи, p – простое число. Тогда, если 5-квадратичный вычет в поле вычетов по модулю p, то un(p-1) ≡ 0(modp), если 5-квадратичный невычет, то un(p+1) ≡ 0(modp). Дается обобщение этого результата на произвольные возвратные последовательности второго порядка. Let un be the n-th Fibonacci number and let p be a prime number. We prove that un(p-1) ≡ 0(modp) if 5 is a quadratic residue in Zp and that un(p+1) ≡ 0(modp) if 5 is the quadratic nonresidue in Zp. A generalization of this result is also obtained for arbitrary recursive sequences of second order. 2012 Article Подільність елементів зворотних послідовностей / А.Г. Матюхіна, Л.Л. Оридорога // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2012. — Т. 25. — С. 161-165. — Бібліогр.: 7 назв. — укр. 1683-4720 http://dspace.nbuv.gov.ua/handle/123456789/124125 531.38 uk Труды Института прикладной математики и механики Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| description |
Нехай un – n-е число Фiбоначчi, p – просте число. Тодi, якщо 5-квадратичний лишок у полi лишкiв за модулем p, то un(p-1) ≡ 0(modp), якщо 5-квадратичний нелишок, то un(p+1) ≡ 0(modp). Дається узагальнення цього результату на довiльнi зворотнi послiдовностi другого порядку |
| format |
Article |
| author |
Матюхіна, А.Г. Оридорога, Л.Л. |
| spellingShingle |
Матюхіна, А.Г. Оридорога, Л.Л. Подільність елементів зворотних послідовностей Труды Института прикладной математики и механики |
| author_facet |
Матюхіна, А.Г. Оридорога, Л.Л. |
| author_sort |
Матюхіна, А.Г. |
| title |
Подільність елементів зворотних послідовностей |
| title_short |
Подільність елементів зворотних послідовностей |
| title_full |
Подільність елементів зворотних послідовностей |
| title_fullStr |
Подільність елементів зворотних послідовностей |
| title_full_unstemmed |
Подільність елементів зворотних послідовностей |
| title_sort |
подільність елементів зворотних послідовностей |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2012 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/124125 |
| citation_txt |
Подільність елементів зворотних послідовностей / А.Г. Матюхіна, Л.Л. Оридорога // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2012. — Т. 25. — С. 161-165. — Бібліогр.: 7 назв. — укр. |
| series |
Труды Института прикладной математики и механики |
| work_keys_str_mv |
AT matûhínaag podílʹnístʹelementívzvorotnihposlídovnostej AT oridorogall podílʹnístʹelementívzvorotnihposlídovnostej |
| first_indexed |
2025-07-09T00:52:53Z |
| last_indexed |
2025-07-09T00:52:53Z |
| _version_ |
1837128612735614976 |
| fulltext |
ISSN 1683-4720 Труды ИПММ НАН Украины. 2012. Том 25
УДК 531.38
c©2012. А.Г. Матюхiна, Л.Л. Оридорога
ПОДIЛЬНIСТЬ ЕЛЕМЕНТIВ ЗВОРОТНИХ ПОСЛIДОВНОСТЕЙ
Нехай un – n-е число Фiбоначчi, p – просте число. Тодi, якщо 5-квадратичний лишок у полi лишкiв
за модулем p, то un(p−1) ≡ 0(modp), якщо 5-квадратичний нелишок, то un(p+1) ≡ 0(modp). Дається
узагальнення цього результату на довiльнi зворотнi послiдовностi другого порядку.
Ключовi слова: подiльнiсть, послiдовнiсть, лишок, поле, число Фiбоначчi, формула Бiне.
1. Вступ. У данiй роботi дослiджено рiзнi задачi на подiльнiсть чисел, що за-
даються арифметичними виразами вiд кореня з цiлого числа D – дискримiнанта
характеристичного рiвняння зворотних послiдовностей II-го порядку. В залежностi
вiд того, чи є D квадратичним лишком за даним простим модулем p, застосовується
один з двох методiв. Якщо D є квадратичним лишком за модулем p, то цей вираз сам
є елементом поля лишкiв за модулем p. Iнакше вiн є елементом розширення даного
поля другого порядку, побудованого за допомогою елемента
√
D. В першому випад-
ку для дослiдження подiльностi застосовується мала теорема Ферма, в другому – її
аналог для скiнченних полiв.
Отриманi результати застосовуються для дослiдження подiльностi спочатку чи-
сел Фiбоначчi, а потiм елементiв довiльних зворотних послiдовностей на простi чис-
ла p. При цьому вiдповiдь суттєво вiдрiзняється, в залежностi вiд того, чи є дискри-
мiнант характеристичного рiвняння послiдовностi квадратичним лишком за моду-
лем p.
Подiльнiсть елементiв зворотних послiдовностей вивчалася багатьма авторами
(див., наприклад, роботи [5]-[7]). У роботi [5] доведено, якщо просте число має
вигляд 5t + 1 або 5t + 1, то p− 1 елемент послiдовностi дiлиться на р. Це доведено
завдяки тому, що бiномiальний коефiцiєнт iз p по k дiлиться на p, де p – просте
[5]. У данiй роботi результат про подiльнiсть чисел Фiбоначчi отримується завдяки
розгляданню розширення поля лишкiв, побудованого за допомогою елемента
√
D
,та застосуванню аналога малої теореми Ферма для скiнченних полiв.
2. Додатковi позначення.
Zp – поле лишкiв за модулем p. Порядок Zp дорiвнює p.
Z∗p – мультиплiкативна група скiнченного поля Zp. Порядок Z∗p дорiвнює p− 1.
Zp[ξ] – множина, яка вийшла розширенням поля Zp за допомогою ξ-кореня
незвiдного рiвняння II-го ступеня, а саме ξ2 − D = 0. Множина Zp[ξ] є полем, так
як виконуються всi властивостi поля. Порядок поля Zp[ξ] дорiвнює p2.
a + bξ та c + dξ та e + fξ – елементи поля Zp[ξ] (a, b, c, d, e, f ∈ Zp).
Z[ξ]∗ – мультиплiкативна група скiнченного поля Z[ξ]. Порядок Z[ξ]∗ дорiвнює
p2 − 1.
This work was awarded the Gold Medal from Yale Science & Engineering Association for Most
Outstanding Eleventh Grade Exhibit in Mathematics at the Intel Isef 2011 Science Fair
161
А.Г. Матюхiна, Л.Л. Оридорога
3. Випадок, коли дискримiнант характеристичного рiвняння є квадра-
тичним лишком у полi лишкiв за простим модулем p.
ai = 1√
5
((
1+
√
5
2
)i
−
(
1−√5
2
)i
)
– формула Бiне для обчислення i-го члена послi-
довностi Фiбоначчi.
При i = n(p− 1), n ∈ Z, p – просте, формула Бiне має вигляд:
an(p−1) =
1√
5
(
1 +
√
5
2
)n(p−1)
−
(
1−√5
2
)n(p−1)
.
Якщо 5-квадратичний лишок за модулем p (у полi Zp), то 1+
√
5
2 ≡ x(modp) та 1−√5
2 ≡
y(modp), тодi формула Бiне перетворюється у такий вигляд:
an(p−1) =
1√
5
(xn(p−1) − yn(p−1)) x, y ∈ Zp,
(p 6= 2 та p 6= 5 – так як формула Бiне у Z2 та у Z5 має дiлення на нуль).
По малiй теоремi Ферма – при p простому i m, яке не дiлиться на p, маємо:
mp−1 ≡ 1(modp).
Якщо m = xn та x 6= 0(modp), тодi xn(p−1) ≡ 1(modp).
Якщо m = yn та y 6= 0(modp), тодi yn(p−1) ≡ 1(modp).
У результатi отримаємо:
an(p−1) ≡
1√
5
(1− 1)(modp);
an(p−1) ≡ 0(modp).
Теорема про подiльнiсть елементiв послiдовностi Фiбоначчi. Якщо 5-
квадратичний лишок у полi лишкiв за модулем p, у Zp, p 6= 2 та p 6= 5, то an(p−1)
член послiдовностi Фiбоначчi {ai} нацiло дiлиться на p, an(p−1) ≡ 0(modp) n ∈ Z, p
– просте.
Узагальнюючи висновок про подiльнiсть елементiв послiдовностi Фiбоначчi {ai}
до будь-якої зворотної послiдовностi {ui}, маємо:
нехай u0 = 0 – виконується для будь-якої зворотної послiдовностi {ui}, тодi вираз
для обчислення n(p− 1) члена послiдовностi {ui} має вигляд:
un(p−1) =
γ√
D
(
a0 +
√
D
2
)n(p−1)
−
(
a0 −
√
D
2
)n(p−1)
, γ ∈ R, (1)
D – дискримiнант характеристичного рiвняння q2 = a0q+b0, зворотної послiдовностi
ui+2 = a0ui+1 + b0ui (a0, b0 ∈ Z), a0+
√
D
2 та a0−
√
D
2 – коренi характеристичного
рiвняння.
162
Подiльнiсть елементiв зворотних послiдовностей
Розглядаючи D, як квадратичний лишок у Zp, та застосовуючи до виразу (1)
малу теорему Ферма, маємо:
un(p−1) ≡ 0(modp),
p 6= 2 та D 6= 0(modp) – так як у виразi (1) є дiлення на цi числа, b0 6= 0(modp) – так
як один iз коренiв характеристичного рiвняння при b0 ≡ 0(modp) дорiвнює нулю.
Теорема про подiльнiсть елементiв зворотних послiдовностей II-го по-
рядку. Якщо дискримiнант характеристичного рiвняння зворотної послiдовностi
II-го порядку {ui} є квадратичним лишком за даним простим модулем p, то un(p−1)
член {ui} нацiло дiлиться на p, un(p−1) ≡ 0(modp), n ∈ Z, p – просте.
4. Випадок, коли дискримiнант характеристичного рiвняння є квад-
ратичним нелишком у полi лишкiв за простим модулем p. Так як порядок
елемента – це ступiнь, в який потрiбно звести елемент, щоб отримати 1 [3]. Порядок
елемента дорiвнює порядку циклiчної пiдгрупи, яка мiстить цей елемент (це вип-
ливає через обмеженiсть пiдгрупи) [3]. У всякої скiнченної групи порядок будь-якої
пiдгрупи є дiльником порядку самої групи (теорема Лагранжа). Iз цього випливає,
що будь-який елемент групи скiнченного поля, зведений у порядок цiєї групи, дорiв-
нює 1.
Застосовуючи дану теорему до груп Zp[ξ]∗ та Z∗p , маємо:
– будь-який елемент iз Zp[ξ]∗, зведений до p2−1, дорiвнює 1, тому (a+bξ)p2−1 = 1;
– будь-який елемент iз Z∗p , зведений до p− 1 дорiвнює 1, тому cp−1 = 1, c ∈ Z∗p .
У множинi Zp[ξ]∗ рiвняння cp−1 = 1 має не бiльше, нiж p−1 коренiв. Це випливає
iз того, що елементiв у множинi Z∗p : p− 1, i кожен iз них є коренем цього рiвняння,
тому iнших коренiв у цьому рiвняннi у полi Zp[ξ]∗ не iснує.
А так як (a + bξ)p2−1 = ((a + bξ)p+1)p−1 = 1 – за ранiше доведеним, тому (a +
bξ)p+1 = c.
Iз цього випливає, що при зведеннi будь-якого елемента iз Zp[ξ]∗ до степеня p+1
ув результатi завжди отримаємо певний елемент, який входить у Z∗p :
(a + bξ)p+1 = a1, a1 ∈ Z∗p .
За допомогою математичної iндукцiї доводиться: якщо спряженi числа iз Zp[ξ]∗ зве-
сти до степеня n, то отримаємо також спряженi числа, якi належать Zp[ξ]∗, тобто
(a + bξ)n = a1 + b1ξ
(a− bξ)n = a1 − b1ξ
(2)
При n = p + 1 та використовуючи, те що (a + bξ)p+1 = a1, a1 ∈ Z∗p , маємо:
(a + bξ)p+1 = a1, a1 ∈ Z∗p
(a− bξ)p+1 = a1, a1 ∈ Z∗p .
I тому
(a + bξ)p+1 = (a− bξ)p+1 = a1.
163
А.Г. Матюхiна, Л.Л. Оридорога
Якщо пiднести обидвi частини рiвнянь (2) до степеня p + 1, отримаємо
((a + bξ)n)p+1 = (a1 + b1ξ)p+1 = a2
((a− bξ)n)p+1 = (a1 − b1ξ)p+1 = a2.
Тому (a + bξ)n(p+1) = (a − bξ)n(p+1). Тому у загальному випадку спряженi числа iз
Z∗p : a + bξ та a − bξ, зведенi у степiнь n(p + 1), де n ∈ Z, p – просте, дорiвнюють
один одному, тобто виконується (a + bξ)n(p+1) = (a− bξ)n(p+1).
Застосуємо данi доведення до формули Бiне послiдовностi Фiбоначчi {ai}:
ai =
1√
5
((
1
2
+
1
2
√
5
)i
−
(
1
2
− 1
2
√
5
)i
)
.
Якщо 1
2 = a, 1
2 = b,
√
5 = ξ, тобто 5-є квадратичним нелишком у Zp, i = n(p + 1), то
an(p+1) =
1√
5
((a + bξ)n(p+1) − (a− bξ)n(p+1)).
За ранiше доведеним (a + bξ)n(p+1) = (a− bξ)n(p+1) маємо:
an(p+1) ≡ 0(modp).
Теорема про подiльнiсть елементiв послiдовностi Фiбоначчi. Якщо 5-
квадратичний нелишок у полi лишкiв за модулем p у Zp, p 6= 2 та p 6= 5, то an(p+1)
член послiдовностi Фiбоначчi {ai} нацiло дiлиться на p, an(p+1) ≡ 0(modp), n ∈ Z, p
– просте.
Узагальнюючи висновок про подiльнiсть елементiв послiдовностi Фiбоначчi {ai}
до будь-якої зворотної послiдовностi {ui}, маємо:
un(p+1) =
γ√
D
((
a0
2
+
1
2
√
D
)n(p+1)
−
(
a0
2
− 1
2
√
D
)n(p+1)
)
, γ ∈ R.
При a = a0
2 , b = 1
2 , ξ =
√
D, D – квадратичний нелишок у Zp, тому вираз для
знаходження n(p + 1) члена послiдовностi {ui} перетворюється у такий вигляд:
un(p+1) =
γ
ξ
((a + bξ)n(p+1) − γ
ξ
((a− bξ)n(p+1)).
А так як (a + bξ)n(p+1) = (a− bξ)n(p+1) за ранiше доведеним, то
un(p+1) ≡ 0(modp).
Iз цього випливає:
Теорема про подiльнiсть елементiв зворотних послiдовностей II-го по-
рядку. Якщо дискримiнант характеристичного рiвняння зворотної послiдовно-
стi II-го порядку є квадратичним нелишком за даним простим модулем p, то
un(p+1) член довiльної зворотної послiдовностi {ui} нацiло дiлиться на p, un(p+1) ≡
0(modp), n ∈ Z, p – просте.
164
Подiльнiсть елементiв зворотних послiдовностей
1. Маркушевич А.И. Возвратные последовательности. – М.: Государственное издательство технико-
теоретической литературы, 1950. – 47 с.
2. Виноградов И.М. Основы теории чисел. – 9-е изд. – М.: Наука, 1981. – 176 с.
3. Курош А.Г. Курс высшей алгебры. — 11-е изд. – М.: Наука, 1975. – 432 с.
4. Кострикин А.И. Введение в алгебру. – М.: Просвещение, 2000. – 493 с.
5. Воробьев Н.Н. Числа Фибоначчи. – 4-е изд. – М.: Наука, 1978. – 144 с.
6. Laslo Geroecs Some properties of divisibility of higher-order linear recursive sequences – Fibonacci
Quarterly, 20, 1982. – P. 354-359.
7. Joseph H. Silverman Divisibility sequences and powers of algebraic integers.Documenta Math. –
Extra Volume Coates, 2006. – P. 711-727.
A.G. Matyukhina, L. L. Oridoroga
Divisibility of recursive sequence elements.
Let un be the n-th Fibonacci number and let p be a prime number. We prove that un(p−1) ≡ 0(modp)
if 5 is a quadratic residue in Zp and that un(p+1) ≡ 0(modp) if 5 is the quadratic nonresidue in Zp. A
generalization of this result is also obtained for arbitrary recursive sequences of second order.
Keywords: divisibility, sequence, residue, field, Fibonacci, Binet formula.
А.Г. Матюхина, Л.Л. Оридорога
Делимость элементов возвратных последовательностей.
Пусть un – n-ое число Фибоначчи, p – простое число. Тогда, если 5-квадратичный вычет в поле
вычетов по модулю p, то un(p−1) ≡ 0(modp), если 5-квадратичный невычет, то un(p+1) ≡ 0(modp).
Дается обобщение этого результата на произвольные возвратные последовательности второго по-
рядка.
Ключевые слова: делимость, последовательность, вычет, поле, число Фибоначчи, формула
Бине.
Донецький нацiональний ун-т
a-l-i-n-a.matyukhina@yandex.ru
Получено 08.06.12
165
|