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

{Результаты данных исследований участвовали на Всеукраинском конкурсе научных работ 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-ой степени, а именно ξ²-D=0.

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

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

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

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

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

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

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

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

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

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

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

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

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

По малой теореме Ферма— при 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)

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

a_{n(р-1)≡15( 1-1)(mod p)};

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

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

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

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

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

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

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

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

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

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

D-дискриминант характеристического уравнения q²=a₀q+b₀ возвратной последовательности u_i+2 = a₀ u_i+1 + b₀ u_i (a_{0 ,b0 ∈} Z);

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

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

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

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

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

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

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

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

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

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

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

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

любой элемент из Z_р[ξ]^*возведенный в р²-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=a₁, a_1∈ Z_р^*

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

При n=p+1 и используя, то что (a+bξ)p⁺¹=a₁, a_1∈Z_р^* , имеем:

(a+bξ) ^p+1=a₁, а_1∈Z_р^*

(a-bξ) ^p+1=a₁, а_1∈Z_р^*

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

Если возвести обе части уравнений (2) в степень p+1, получим

((a+bξ)n)^p+1= (a₁+b₁ξ)^p+1=a₂

((a-bξ)n)^p+1= (a₁-b₁ξ)^p+1=a₂

Поэтому (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).

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

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

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

Если 12= a

12=b

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

i=n(p+1)

То a_n(p+1)=15( a+b ξ^{n(p+1)-a-b ξn(p+1))}

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

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

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

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

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

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

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

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

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

При а= а02

b= 12

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

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

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

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

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

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

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

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

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

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

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

простое число.Например, для последовательности с возвратным уравнениемun₊₂ = -5un₊₁ +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₊₂ =-5un₊₁ +3un: u₅₂ u₁₀₄, u₁₅₆, u_208, u_260, u_312, u₃₆₄, u₄₁₆, u₄₆₈,….. ,

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

Вычислим u₅₂ и проверим целочисленное деление 52-го члена последовательности un₊₂ =-5un₊₁ +3un на простое число 53 :

u₅₂=1√37((-52+1237)⁵²-(-52-1237)⁵²)= -76566149231037415213602340833101530715

-76566149231037415213602340833101530715/ 53=

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

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

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

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

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

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

a_i-a_j≡0(mod 1999)

a_i+1-a_j+1≡0(mod 1999)

Так как a₁, a₂, a₃,… -элементы последовательности с возвратным уравнением

a_j+2 =a_j+1 +a _j ,

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

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

а₂-а_j+1≡0(mod 1999)

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

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

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

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

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

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

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

a_j+2 =a_j+1 +a _j имеет вид:

a_j=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)

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

1050^j-1-950^j-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)⁷-x⁷-y⁷ делится на 7⁷

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

Решение

(x+y)⁷-x⁷-y⁷=7⁷*k, k ∈ Z |*1y

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

Замена xy =a

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

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

a₂= -1--32 а₃= -1+-32

Докажем это:

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

a₁=1

a₂=cos2π3+isin2π3

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

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

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

(a₃+1)⁷ =a₃+1

a₂⁷= a₂

a₃⁷= a₃

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

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

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

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

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

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

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

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

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

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

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

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

(a +1)⁷-a⁷-1≡0(mod 6k₁+1) .

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

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

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

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

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г.)

Код для цитирования: Скопировать