ДЕЛИМОСТЬ ЭЛЕМЕНТОВ ВОЗВРАТНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ - Студенческий научный форум

V Международная студенческая научная конференция Студенческий научный форум - 2013

ДЕЛИМОСТЬ ЭЛЕМЕНТОВ ВОЗВРАТНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

Матюхина А.Г. 1
1Донецкий национальный университет, Украина
 Комментарии
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
{Результаты данных исследований участвовали на Всеукраинском конкурсе научных работ Intel Eko (национальный тур международного конкурса Intel ISEF) занято третье место в категории "Компьютерные науки. Математика",получен сертификат на дальнейшее участие в международном конкурсе компьютерных наук INFORMATRIX (Бухарест, Румыния).

Получена золотая медаль "Yale Science & Engineering Association Medallion" за лучшую работу в категории «Математика» от Йельского университета (США).(2011г.)

Стала лауреатом международного конкурса научных работ до 18 лет. (г. Москва,2012г.)

Данная работа опубликована:

  1. 2013, г. Донецк журнал « Труды Института прикладной математики и механики» Донецк, Украина .

  2. 2012, г. Луганськ , сборник трудов II-ой Международной научно-практичной Інтернет-конференции 2012 среди молодих ученых «Научная молодеж: инновационные подходы к образованию и науке

  3. 2012, сборник трудов международной конференции SWorld «Современные направлениятеоретических и прикладных исследований» }

Аннотация

В данной работе исследованы различные задачи на делимость чисел, задаваемые арифметическими выражениями от корня из целого числа D-дискриминанта характеристического уравнения возвратных последовательностей II-го порядка.

В зависимости от того, является ли D квадратичным вычетом по данному простому модулю p, применяется один из двух методов. Если D является квадратичным вычетом по модулю р, то это выражение само является элементом поля вычетов по модулю р. Иначе оно является элементом расширения данного поля второго порядка, построенного с помощью элемента D. В первом случае для исследования делимости применяется малая теорема Ферма, во втором - ее аналог для конечных полей. Полученные результаты применяются для исследования делимости сначала чисел Фибоначчи, а затем элементов произвольных возвратных последовательностей, на простые числа р. При этом ответ существенно отличается, в зависимости от того, является ли дискриминант характеристического уравнения последовательности квадратичным вычетом по модулю р.Также эти методы применяются к решению и обобщению олимпиадных задач на делимость. В работе разобраны задача # 4 XI класса ХХХIХ-й всеукраинской математической олимпиады и задача # 2 ХХV-й международной математической олимпиады.

Дополнительные обозначения

Zр- поле вычетов по модулю р. Порядок Zр равен р.

Zр*- мультипликативная группа конечного поля Zр. Порядок Zр* равен р-1.

Zр[ξ] –множество, которое вышло расширением поля Zр с помощью корня ξ –корня неприводимого уравнения II-ой степени, а именно ξ2-D=0.

Множество Zр[ξ] является полем, так как выполняются все свойства поля.

Порядок поля Zр[ξ] равен р2.

a+b ξ та с+d ξ та e+f ξ – элементы поля Zр[ξ] ( a, b, с, d, e, f ∈ Zр).

Из этого следует, что ξ2= D – квадратичный невычет по модулю p, в Zр.

Zр[ξ]*- мультипликативная группа конечного поля Zр[ξ]. Порядок Zр[ξ]* равен р2-1.

Случай, когда дискриминант характеристического уравнения является квадратичным вычетом в поле вычетов

по простому модулю р

aі= 15 1+52і-1-52і — формула Бине для вычисления і-го члена последовательности Фибоначчи.При i=n(p-1), n∈Z, p— простое, формула Бине имеет вид:

an(р-1)= 15 1+52nр-1-1-52nр-1.

Если 5— квадратичный вычет по модулю p (в поле Zp), то

1+52≡х (mod p) та 1-52≡у (mod p)

тогда формула Бине имеет такой вид: an(р-1)= 15( хn(р-1)-уn(р-1)) х,у∈ Zp ,

(р≠2 и р≠5— так как формула Бине в Z2 и в Z5 имеет деление на нуль).

По малой теореме Ферма— при p простом и m, которое не делится на p, имеем:

mp-1≡1 (mod p)

Если m=xn и x≢0(mod p), тогда хn(p-1)≡1 (mod p)

Если m=yn и y≢0(mod p), тогда yn(p-1)≡1 (mod p)

В результате получим:

an(р-1)≡15( 1-1)(mod p);

an(р-1)≡ 0(mod p)

Теорема 1«О делимости элементов последовательности Фибоначчи»:

«если 5квадратичный вычет в поле вычетов по модулю р, в Zр, р≠2 и р≠5,

то an(p-1) член последовательности Фибоначчи {aі} нацело делится на p,

an(p-1)≡0(mod p) n∈Z, р— простое.»

Обобщая вывод о делимости элементов последовательности Фибоначчи

{ai} до любой возвратной последовательности {ui}, имеем:

Пусть u0=0— выполняется для любой возвратной последовательности {ui},

тогда выражение для вычисления n (p-1) члена последовательности {ui}имеет вид:

un(р-1)=γD a0+D2nр-1-a0-D2nр-1 γ∈ R (1)

D-дискриминант характеристического уравнения q2=a0q+b0 возвратной последовательности ui+2 = a0 ui+1 + b0 ui (a0 ,b0 ∈ Z);

a0+D2 та a0-D2 — корни характеристического уравнения

Рассматривая D, как квадратичный вычет в Zр и применяя к выражению (1) малую теорему Ферма, имеем:un(р-1)≡ 0(mod p)

p≠2 та D≢0(mod p) — так как в выражении (1) есть деление на эти числа;b0≢0(mod p) — так как один из корней характеристического уравнения при b0≡0(mod p) равен нулю.

Из этого следует-

Теорема 2 «О делимости элементов возвратных последовательностей

II-го порядка»:

«Если дискриминант характеристического уравнения возвратной последовательностиII-го порядка является квадратичным вычетом по данному простому модулю р, то un(p-1) член произвольной возвратной последовательности {ui} нацело делится на p, то есть выполняется

un(p-1)≡0(mod p) n∈Z, р — простое.»

Случай, когда дискриминант характеристического уравнения является квадратичным невычетом в поле вычетов

по простому модулю р

Так как порядок элемента - это степень, в которую нужно возвести элемент для того, чтобы получить 1. Порядок элемента равен порядку циклической подгруппы содержащей этот элемент (это следует из ограниченности подгруппы). У всякой конечной группы порядок любой подгруппы является делителем порядка самой группы (теорема Лагранжа). Из этого следует, что любой элемент группы конечного поля возведенный в порядок этой группы равен 1.

Применяя данную теорему к группам Zр[ξ]* та Zр*, имеем:

любой элемент из Zр[ξ]*возведенный в р2-1 степень равен 1,

поэтому (a+bξ)p2-1= 1;

любой элемент из Zр*возведенный в р-1 степень равен 1,

поэтому cp-1=1, c ∈ Zр*

В множестве Zр[ξ]* уравнение cp-1=1 имеет не более чем р-1 корней. Это следует из того, что элементов в множестве Zр* р-1, и каждый из них является корнем этого уравнения, поэтому других корней в этом уравнении в поле Zр[ξ]* не существует.

А так как (a+bξ)p2-1 = ((a+bξ) p+1)p-1=1- по ранне доказанному,

поэтому (a+bξ) p+1=с.

Из этого следует, что при возведении любого элемента из Zр[ξ]* в степень p +1 в итоге всегда получим определенный элемент, входящий в Zр*.

(a+bξ) p+1=a1, a1∈ Zр*

С помощью математической индукции доказывается: Если сопряженные числа из Zр[ξ]* возвести в степень n, то получим также сопряженные числа, принадлежащие Zр[ξ]* , т.е. (a+bξ)n= a1+b1ξ(2) (a-bξ)n= a1-b1ξ

При n=p+1 и используя, то что (a+bξ)p+1=a1, a1∈Zр* , имеем:

(a+bξ) p+1=a1, а1∈Zр*

(a-bξ) p+1=a1, а1∈Zр*

И поэтому (a+bξ) p+1=(a-bξ) p+1

Если возвести обе части уравнений (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)

Поэтому в общем случае: Сопряженные числа из Zр*-a+b ξ та a-b ξ возведенные в степень n(p+1), где

n ∈Z,р-простое , равны друг другу, т.е. выполняется (a+b ξ)n(p+1)=(a-b ξ)n(p+1).

Применим данные доказательства к формуле Бине последовательности

Фибоначчи {ai}:

ai=15( 12+125i-12-125i)

Если 12= a

12=b

5= ξ, то есть 5- квадратичный невычит в Zр

i=n(p+1)

То an(p+1)=15( a+b ξn(p+1)-a-b ξn(p+1))

По ранне доказанному (a+bξ)n(p+1)=(a-bξ)n(p+1) имеем:

an(p+1)≡0(mod p)

Теорема 3 «О делимости элементов последовательности Фибоначчи»:

«если 5квадратичный невычет в поле вычетов по модулю р, в Zр, р≠2 и р≠5,

то an(p+1) член последовательности Фибоначчи {aі} нацело делится на p,

an(p+1)≡0(mod p) n∈Z, р— простое.»

Обобщая вывод о делимости элементов последовательности Фибоначчи

{ai} до любой возвратной последовательности {ui}, имеем:

un(р+1)= γD( a02+12Dnр+1-a02-12Dnр+1) γ∈ R

При а= а02

b= 12

ξ=D, D-квадратичный невычет в Zp,

поэтому выражение для нахождения n (p +1) члена последовательности {ui} превращается в такой вид:

un(р+1)= γ ξ а+bξnр+1-а-bξnр+1

А так как (a+bξ)n(p+1)=(a-bξ)n(p+1) – по раннее доказанному ,то

un(р+1)≡0 (mod p)

Из этого следует —

Теорема 4 «О делимости элементов возвратных последовательностей

II-го порядка»:

«Если дискриминант характеристического уравнения возвратной последовательностиII-го порядка является квадратичным невычетом по данному простому модулю р, то un(p+1) член произвольной возвратной последовательности {ui} нацело делится на p

un(p+1)≡0(mod p) n∈Z, р — простое.»

Используя данные теоремы для произвольной возвратной последовательности, сможем указать номера членов данной последовательности (без вычисления элементов последовательности), которые нацело делятся на данное нам

простое число.Например, для последовательности с возвратным уравнениемun+2 = -5un+1 +3un:

Простые числа

От 0 до 100

р

Члены последовательности un+2 =-5un+1 +3un,

которые делятся без остатка на р:

Общая

формула

S=1

S=2

S=3

S=4

S=5

S=6

S=7

S=8

S=9

S=…

 

5

u6

u12

u18

u24

u30

u36,

u42

u48

u54

u6s

7

u6

u12

u18

u24

u30

u36

u42

u48

u54

u6s

11

u10

u20

u30

u40

u50

u60

u70,

u80

u90

u10s

13

u14

u28

u42

u56

u70

u84

u98

u112

u126

u14s

17

u18

u34

u51

u68

u85

u102

u119,

u136

u153

u17s

19

u20

u40

u60

u80

u100

u120

u140

u160

u180

u20s

23

u24

u48

u72

u96

u120

u144

u168

u192

u216

u24s

29

u30

u60

u90

u120

u150

u180

u210

u240

u270

u30s

31

u32

u64

u96

u128

u160

u192

u224

u256

u288

u32s

37

u36

u72

u108

u144

u180

u216

u252

u288

u324

u36s

41

u40

u80

u120

u160

u200

u240

u280

u320

u360

u40s

43

u42

u84

u126

u168

u210

u252

u294

u336

u378

u42s

47

u46

u92

u138

u184

u230

u276

u322

u368

u414

u46s

53

u52

u104

u156

u208

u260

u312

u364

u416

u468

u52s

59

u60

u120

u180

u240

u300

u360

u420

u480

u540

u60s

61

u62

u124

u186

u248

u310

u372

u434

u496

u558

u62s

67

u66

u132

u198

u264

u330

u396

u462

u528

u594

u66s

71

u70

u140

u210

u280

u350

u420

u490

u560

u630

u70s

73

u72

u144

u216

u288

u360

u438

u504

u576

u648

u72s

79

u80

u160

u240

u320

u400

u480

u560

u640

u720

u80s

83

u82

u164

u246

u328

u410

u492

u574

u656

u738

u82s

89

u90

u180

u270

u360

u450

u540

u630

u720

u810

u90s

97

u98

u196

u294

u392

u490

u588

u686

u784

u882

u98s

В даной таблицы видно, что на простое число 53 делятся следующие члены последовательности un+2 =-5un+1 +3un: u52 u104, u156, u208, u260, u312, u364, u416, u468,….. ,

следовательно все члены последовательности в виде u52s , где s- произвольное целое число.

Вычислим u52 и проверим целочисленное деление 52-го члена последовательности un+2 =-5un+1 +3un на простое число 53 :

u52=1√37((-52+1237)52-(-52-1237)52)= -76566149231037415213602340833101530715

-76566149231037415213602340833101530715/ 53=

= -1444644325113913494596270581756632655– целое число

Из этого следует, что наша теория работает, результат деления-целое число.

Олимпиадное задание Заключительного этапа 39 - ой Всеукраинской олимпиады по математике 1999 года: Решение

У второго игрока есть две выигрышные стратегии: 1) если a1≡0(mod 1999) ,то a2≢0(mod 1999)

2) если а1≢0(mod 1999),то a2≡0(mod 1999)

Докажем, что они обе являются выигрышные: Предположим, что игра закончилась, тогда

ai-aj≡0(mod 1999)

ai+1-aj+1≡0(mod 1999)

Так как a1, a2, a3,… -элементы последовательности с возвратным уравнением

aj+2 =aj+1 +a j ,

тогда ai-1-aj-1= (ai+1-ai)-(aj+1-aj)= (ai+1- aj+1)-( ai -aj) и поэтому ai-1-aj-1≡0(mod 1999).

Приходим к выводу, что наименьший индекс і при котором второй игрок выиграет будет і=1, т.е. будет выполняться: а1j≡0(mod 1999)

а2j+1≡0(mod 1999)

Рассматривая последовательность остатков от деления записанных чисел a1, a2, a3,… на 1999, нетрудно доказать, что игра конечна (по принципу Дирихле). Поэтому, если a1≡0(mod 1999), то и aj≡0(mod 1999)

Заметим, что достаточно рассмотреть случай, когда

a1≡0(mod 1999) при a2≢0(mod 1999), последовательность остатков имеет вид 0,а,а,2а,…..,0,а,а,2а…( В случае, когда а1≢0(mod 1999) при a2≡0(mod 1999)

последовательность остаток будет аналогичной, со смещением на один элемент а,0,а,а,2а,…..а,0,а,а,2а…. )

И остается доказать, что разница между порядковыми номерами пары

a1≡0(mod 1999) , a2≢0(mod 1999) и пары aj≡0(mod 1999), aj+1≢0(mod 1999) последовательности 0,а,а,2а,…..,0,а,а,2а…- четное число.

Формула для вычисления aj члена последовательности с возвратным уравнением

aj+2 =aj+1 +a j имеет вид:

aj=5-125a1 +15a2 1+52j-1+ 5+125a1-15a2 1-52j-1

при а1≡0(mod 1999), получим-

аj= 15a2 ( 1+52j-1-1-52j-1)

Так как аj≡0(mod 1999), то

1+52j-1-1-52j-1≡0(mod 1999)

Так как 5-квадратичный вычет в поле вычетов по модулю1999

5≡100(mod 1999) ,то

1+52≡1050(mod 1999)

1-52≡950(mod 1999)

Поэтому сравнение превращается в такой вид:

1050j-1-950j-1≡0(mod 1999)

Так как

11-52 = 21-√5= 2(1+5)1-5=2(1+5)(-4)=-(1+5)2

Получим, что 950≡ -11050(mod 1999)

Поэтому наше сравнение превращается в такой вид: 1050 j-1 - (-11050)j-1 ≡0(mod 1999)

(-1)j-1 10502 (j-1)≡1(mod 1999)

Возведем обе части сравнения в степень 999, получим

(-1)j-110501998(j-1)≡1 (mod 1999)

По малой теореме Ферма- 10501998≡1 (mod 1999)

Возведем обе части сравнения в степень (j-1), получим

10501998(j-1)≡1(j-1) mod 1999 Поэтому при подстановки сравнений, получим: (-1)j-1(1)j-1≡1 (mod 1999)

(-1)j-1≡1 mod 1999- верно, только при нечетном j , что и требовалось доказать.

Олимпиадное задание 25 - ой международной олимпиады по математике 1984 года:

“ Существует ли пары целых чисел x и y такие, что xy(x+y) не делится на 7 , а (x+y)7-x7-y7 делится на 77

Обоснуйте свой ответ.’’

Решение

(x+y)7-x7-y7=77*k, k ∈ Z |*1y

(xy+1)7 –(xy)7-1≡0(mod 7)

Замена xy =a

(a +1)7-a7-1≡0(mod 7)

Уравнению (a +1)7-a7-1=0 удовлетворяют два решения уравнения a=31, а именно

a2= -1--32 а3= -1+-32

Докажем это:

На комплексной плоскости решения уравнения a=31 :

a1=1

a2=cos2π3+isin2π3

a3=cos4π3+isin4π3 -вершины правильного треугольника, тогда точка a2+1 является вершиной правильного шестиугольника, поэтому a2+1=61=cosπ3+isinπ3

Воспользовавшись формулой Муавра докажем, что (a2+1)7=(cosπ3+isinπ3)7=cos7π3+isin7π3=cosπ3+isinπ3= a2+1

Аналогично доказывается, что

(a3+1)7 =a3+1

a27= a2

a37= a3

Если a2=а=cos2π3+isin2π3= -1--32

а3=а=cos4π3+isin4π3 = -1+-32

Тогда (a +1)7-a7-1≡0(mod 7) - что и требовалось доказать. Так как -3 – квадратичный вычет в поле вычетов по модулю 7

-3≡ 7-3≡ 4 ≡2(mod 7)

Из этого следует, что сравнение (a +1)7-a7-1≡0(mod 7) имеет два решения

а= a2=4(mod 7) та а=a3=2(mod 7), а так як xy = a, тогда и сравнение

(xy+1)7 –(xy)7-1≡0(mod 7) имеет решение, поэтому приходим к выводу, что существуют такие пары целых чисел x и y которые удовлетворяют условию - xy(x+y) не делится на 7 , а (x+y)7-x7-y7 делится на 77 (в моей работе эти пары чисел найдены::(77m+58l; 14m+15l) де m, l ∈Z- первая пара чисел

(161m+143l; 28m+27l) де m, l ∈Z- вторая пара чисел)

Обобщение: В данной задаче мы видим, что сравнение (a +1)7-a7-1≡0(mod 7) выполняется только в том случае, когда -3 является квадратичным вычетом в поле вычетов по модулю 7, в Z7.

А так как -3 является квадратичным вычетом в поле вычетов по модулю

p=6k1+1, k1 є Z(доказывается с помощью символа Лежандра).

Тогда будет выполняться такое сравнение-

(a +1)7-a7-1≡0(mod 6k1+1) .

Для этого сравнения p=6k1+1,k1 є Z- необходимое и достаточное условие.

А для сравнения (a +1) 6k1 +1-a 6k1 +1-1≡0(mod 6k1+1), p=6k1+1- только достаточное условие. Если -3- квадратичный вычет по модулю р, то -3 - квадратичный вычет по модулю рm.

Из этого следует, если n=6k+1, p=6l+1- простые числа, m-произвольное натуральное, то существуют такие х, у, что xy(x+y)≢0(mod p)и в то же время (x+y)n-xn-yn0(mod pm).

Список использованной литературы:

1. Маркушевич А.И. Возвратные последовательности.-1950.-с.3-47.

2. Виноградов И.М.Основы теории чисел.-1981.- с.17-21,38-82.

3. J.H. Silverman, Common divisors of an − 1 and bn − 1 over function fields,New York Journal of Math. (electronic) 10 (2004), 37–43.

4. Marcellus E. Waddill. "Some Properties of a Generalized Fibonacci Sequence Modulo m." The Fibonacci Quarterly 16, No. 4 (August 1978), 344-353.4. физико-математический журнал КВАНТ для школьников и студентов №2

март/апрель // Л.Шибасов,З.Шибасова «Кролики Фибоначчи».-2005.- с.7-10.

5. Кострикин А.И. Введение в алгебру.-2000.-с.8-493.

6. Н.Н. Воробьев Числа Фибоначчи.-1978.-с.3-115.

Результаты данных исследований участвовали на Всеукраинском конкурсе научных работ Intel Eko (национальный тур международного конкурса Intel ISEF) занято третье место в категории "Компьютерные науки. Математика",получен сертификат на дальнейшее участие в международном конкурсе компьютерных наук INFORMATRIX (Бухарест, Румыния).

Получена золотая медаль "Yale Science & Engineering Association Medallion" за лучшую работу в категории «Математика» от Йельского университета (США).(2011г.)

Стала лауреатом международного конкурса научных работ до 18 лет. (г. Москва,2012г.)

Просмотров работы: 1698