Регистрирайте сеРегистрирайте се

Теория на числата (ТЧ)


 
   Форум за математика Форуми -> Теория свързана с олимпиади
Предишната тема :: Следващата тема  
Автор Съобщение
Мирослав Стоенчев
Напреднал


Регистриран на: 21 Aug 2007
Мнения: 279

Репутация: 72
гласове: 45

МнениеПуснато на: Sat Sep 29, 2007 3:56 pm    Заглавие: Теория на числата (ТЧ)

Тук ще бъде изложен сбито необходимият теоретичен материал по ТЧ, улесняващ подготовката за средношколски състезания.

Последната промяна е направена от Мирослав Стоенчев на Sat Feb 09, 2008 5:25 pm; мнението е било променяно общо 2 пъти
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Реклама







Пуснато на:     Заглавие: Реклама

Върнете се в началото
Мирослав Стоенчев
Напреднал


Регистриран на: 21 Aug 2007
Мнения: 279

Репутация: 72
гласове: 45

МнениеПуснато на: Sat Sep 29, 2007 4:39 pm    Заглавие:

1.Делимост -Разглеждаме само цели числа.Ако a≠0 и b са цели записваме а|b и казваме,че a дели b,когато съществува цяло c: ac=b.

деф.НОД и НОК. Ако a и b са цели числа,поне едното от които е различно от 0, съществува положително число d със следните свойства:
1) d|a и d|b
2) ako u|a и u|b => u|d
Числото d се нарича НОД на a и b, записва се d=(a,b).

НОК[а,b]=m=[a,b], най-малкото общо кратно на а и b е число m със следните свойства:
1') a|m и b|m
2') Ако v е общо кратно на a и b, то m|v.

В сила е равенството [а,b](a,b)=ab

Теорема за деление с частно и остатък. - Нека а и b са цели, като b>0.Съществуват цели q и r за които а=bq+r, 0≤r≤b-1. Тук q се нарича частно, a r- остатък.

Прости числа- едно естествено число p>1 се нарича просто, ако освен себе си и 1 няма други естествени делители.

Основна теорема на аритметиката - всяко естествено число, различно от 1, може да се представи като произведение на краен брой прости числа.Това представяне е единствено с точност до реда, в който са записани множителите.
Разлагането на дадено естествено число в произведение на прости множители се нарича канонично разлагане. Например:
n=(p1)α1...(pn)αn

Теорема на Евклид. Съществуват безбройно много прости числа.

Теорема на Дирихле. Всяка безкрайна аритметична прогресия с взаимнопрости първи член и разлика, (т.е. (а,d)=1 , където прогресията е а, а+d, ... , a+kd,... ) съдържа безбройно много прости числа.

Теорема на Чебишев. Ако n>1 e естествено число, то съществува просто число p, за което n<p<2n.

Функцията [x] - Нека x е произволно реално число.Със [x] означаваме най-голямото цяло число, което е по-малко или равно на x.
Теорема за [x]. Ако n е естествено число а p-просто, то степента с която p участва в каноничното разлагане на n!=1.2...n на прости множители е равна на
[n/p]+[n/p2]+...+[n/pk]+...
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Мирослав Стоенчев
Напреднал


Регистриран на: 21 Aug 2007
Мнения: 279

Репутация: 72
гласове: 45

МнениеПуснато на: Sun Sep 30, 2007 10:46 am    Заглавие:

2.Сравнения - ако m е естествено число и a,b са цели, ще казваме,че a е сравнимо с b по модул m и ще пишем a≡b(mod m), когато m|a-b, т.е. когато m дели a-b.Ясно е че a≡b(mod m) тогава и само тогава,когато числата a и b имат един и същи остатък по модул m.

Основни свойства на сравненията:
1) За всяко а е в сила a≡а(mod m)
2)Ако a≡b(mod m), то b≡a(mod m)
3)Aко a≡b(mod m) и b≡c(mod m), то а≡c(mod m)
4)Aко a≡b(mod m) и c≡d(mod m), то a+c≡b+d(mod m) и ac≡bd(mod m)
5)Aко ac≡bc(mod m), то a≡b(mod m/(m,c)).В частност, ако нод(m,c)=1,от ac≡bc(mod m) =>
a≡b(mod m)

Функция на Ойлер. Нека n е естествено число.С ф(n) означаваме броя на естествените числа по-малки от n и взаимно прости с n.Основни свойства на ф(n)функцията на Ойлер:
1)Ако n=pα е степен на простото число p, то ф(pα)=pα-pα-1
2)Ако (m,n)=1,то ф(mn)=ф(m)ф(n)
3)Aко n=(p1)α1(p2)α2...(pk)αk,то
ф(n)=n(1-1/p1)(1-1/p2)...(1-1/pk)

Теорема на Ойлер. Ако (а,n)=1, то aф(n)≡1(mod n)

Teорема на Ферма(частен случай на Теоремата на Ойлер).Полагаме n=p-просто число, тогава ф(p)=p-1 => Th на Ферма: Ако p не дели а, то аp-1≡1(mod p).

Теорема на Уилсон. Едно естествено число [tex]p>1[/tex] е просто тогава и само тогава, когато е изпълнено сравнението [tex](p-1)!+1\equiv 0(mod (p))[/tex]


Последната промяна е направена от Мирослав Стоенчев на Sat Nov 24, 2007 6:01 pm; мнението е било променяно общо 1 път
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Мирослав Стоенчев
Напреднал


Регистриран на: 21 Aug 2007
Мнения: 279

Репутация: 72
гласове: 45

МнениеПуснато на: Sun Sep 30, 2007 5:13 pm    Заглавие:

3. Диофантови уравнения

3.1 Уравнението x2+y2=z2
Всички решения на уравнение 3.1 са {x,y}={2duv,d(u2-v2}, z=d(u2+v2), където u,v са взаимнопрости естествени числа от различна четност, а d е произволно естествено.

3.2 Уравнение на Пел. x2-dy2=1, където d не е точен квадрат.
Уравнението 3.2) има безбройно много решения.Всички положителни решения се задават чрез формулата xn+yn√d=(x1+y1√d)n.
Tук (x1,y1) e минималното положително решение на 3.2), а при n=1,2,... получаваме всички решения на 3.2).

3.3 Уравнение на Ферма. xn+yn=zn, няма решения в цели числа различни от (0,0,0) при n>2.

Th -1.Ако q e просто число от вида 4k+3 и q|a2+b2, то
q|a и q|b.

Например уравнението x2+y2=qz2 при q -просто число от вида 4k+3, няма решение в естествени числа.Да допуснем противното и нека (а,b,c) e решение,като
c- e минимално.Понеже а2+b2=qc2 => q|a2+b2 =>q|a и q|b =>q|c. Значи a=qa', b=qb', c=qc'.Заместваме в началното уравнение и получаваме а'2+b'2=qc'2, kато c'=c/q<c и (а',b',c') е решение на началното уравнение.Противоречие с минималността на c.Tук приложихме "метода" на Ферма на "безкрайното спускане".

Ако p e просто число от вида 4к+1, то p=x2+y2, за някакви естествени x и y.Вярно е и обратното - ако p=x2+y2 и p е просто, то p е от вида 4к+1.

Th(Лагранж). Всяко естествено число може да се представи като сума на 4 цели квадрата.(т.е. 4 цели квадрата са достатъчни, някои може да са нули)

Китайска теорема за остатъците.Ако n1,n2,...,nr са две по две взаимнопрости естествени числа, то съществува цяло число x удовлетворяващо системата сравнения |x≡ai(mod ni), за всяко i=1,2,...,r.

Th.Ako нод(a1,a2,...,an)=d, където аi≠0, то съществуват цели числа xi такива,че ∑аixi=d, тук сумирането е по i=1,2,...,n.

Следствие.Ако (а,b)=1, то съществуват цели u,v: au+bv=1.

Лема на Туе.Нека n>1 е естествено число.Тогава за всяко а: (а,n)=1, съществуват естествени числа x,y по малки или равни на [√n] такива,че ax≡+-y(mod n).
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Мирослав Стоенчев
Напреднал


Регистриран на: 21 Aug 2007
Мнения: 279

Репутация: 72
гласове: 45

МнениеПуснато на: Tue Oct 02, 2007 7:59 pm    Заглавие:

3. Диофантови уравнения (продължение)

Приложение метода на Ферма за "безкрайното спускане"

Теорема на Ферма. Диофантовото уравнение x4-y4=z2
няма решения в естествени числа x,y и z.
Д-во:Да допуснем противното- (x,y,z) е решение на уравнението.Полагаме (x,y)=d,
x=dx1, y=dy1, тогава от уравнението следва,че z/d2=z1 e цяло.Така стигнахме до уравнението (x1)4-(y1)4=(z1)2.
Понеже (x1,y1)=1, то (x1,z1)=(y1,z1)=1.
Значи е достатъчно да покажем,че изходното диоф. уравнение няма решение в две по две взаимнопрости x,y,z. Нека (x,y)=(y,z)=(z,x)=1,като (x,y,z) е решение на уравнението и x е минимално.Тогава точно едно от числата x,y,z е четно.Понеже y4+z2 е нечетно, то y или z е четно.

1сл. y- четно.
Понеже (x2+z,x2-z)=2 и 16|(x2+z)(x2-z) следва,че 8 дели x2+z, а 2 дели x2-z или обратно.
Тогава числата (x2+z)/2 и (x2-z)/8 са взаимно прости, като произведението им е точен биквадрат. Тогава всяко едно от тях е биквадрат, т.е.
съществуват взаимнопрости естествени числа a,b такива,че x2+z=2а4 и x2-z=8b4.Събираме ги и получаваме x2=a4+4b4 => (x2+a)(x2-a)=4b4.
Имаме,че нод(x2-a,x2+a)=2 => x2-a=2c2 и x2+a=2d2.
Значи а2=c4-d4, т.е. (c,d,a) е решение на изходното уравнение, като c<2acd=y<x, което е противоречие с минималността на x.

2сл. z е четно. Записваме уравнението във вида (x2+y2)(x2-y2)/4=z2
Понеже нод(x2+y2,x2-y2)=2, а произведението на тези числа е точен квадрат, то всяко от тях е точен квадрат, т.е.
(x2+y2)/2=а2,(x2-y2)/2=b2
Тогава x=а2+b2, y=а2-b2 =>
(xy)2=a4-b4.
Получихме,че (a,b,xy) е решение на изходното уравнение, като а<(a2+b2)1/2=x. Отново противoречие с минималността на x.
Цитираното доказателство принадлежи на Ферма!


Със същия метод се доказва,че уравненията x4+y4=z2 и
x4-y4=2z2
нямат решения в естествени числа.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Мирослав Стоенчев
Напреднал


Регистриран на: 21 Aug 2007
Мнения: 279

Репутация: 72
гласове: 45

МнениеПуснато на: Mon Nov 19, 2007 2:45 pm    Заглавие:

4. Доказателства на основните Теореми



Теорема на Евклид. Съществуват безбройно много прости числа.

Д-во: (Евклид) Да допуснем противното, и нека [tex]p_{1},p_{2},...,p_{n}[/tex] са всичките прости числа, като [tex]p_{1}<p_{2}<...<p_{n}[/tex].Тогава [tex]p_{1}=2, p_{2}=3, ...[/tex].
Да разгледаме числото [tex]N=p_{1}p_{2}...p_{n}+1[/tex].To е нечетно и не се дели на никое от числата [tex]p_{1},p_{2},...,p_{n}[/tex], понеже е взаимнопросто с всяко от тях.
Съгласно основната теорема на аритметиката, числото [tex]N[/tex] се представя като произведение на прости множители.Вече знаем, че никой измежду последните не е от редицата [tex]p_{1},p_{2},...,p_{n}[/tex]. Следователно или [tex]N[/tex] е ново просто число, или се представя като произведение на прости числа различни от [tex]p_{1},p_{2},...,p_{n}[/tex].Противоречие.Следователно допускането ни е невярно, т.е. доказахме съществуването на безбройно много прости числа.


Теорема на Чебишев. Ако [tex]n>1[/tex] е естествено число, то съществува просто число [tex]p[/tex], за което [tex]n\le p<2n[/tex].

Д-во: (С. С. Пиллаи) Ще изпозлзваме означението [tex]N=\frac{(2n)!}{(n!)^{2}[/tex], за
биномния коефициент. Ще докажем неравенството [tex] 1) \frac{2^{2n}}{2\sqrt{n}}<N<\frac{2^{2n}}{\sqrt{2n}}[/tex], при [tex]n\ge 2[/tex].
Полагаме [tex]P=\frac{1.2.3...(2n-1)}{2.4.6....(2n)}=\frac{1.2.3...(2n-1)}{2.4.6....(2n)} \frac{2.4.6...(2n)}{2.4.6...(2n)}=\frac{(2n)!}{2^{2n}(n!)^{2}}[/tex]
Значи
[tex]N=2^{2n}P[/tex]. Също така в сила е неравенството [tex]1>(1-(2)^{-2})(1-(4)^{-2})...(1-(2n)^{-2})[/tex], което го записваме така:
[tex]1>(2n+1)P^{2}>2nP^{2}=\frac{2n}{2^{4n}}N^{2}[/tex], oт където следва неравенството[tex]N<\frac{2^{2n}}{\sqrt{2n}}[/tex]
За да докажем другото неравенство, използваме очевидното [tex]1>(1-(3)^{-2})(1-(5)^{-2})...(1-(2n-1)^{-2})[/tex], от където получаваме [tex]1>\frac{1}{4nP^{2}}=\frac{2^{4n}}{4nN^{2}}[/tex]. Така получаваме, че [tex]\frac{2^{2n}}{2\sqrt{n}}<N[/tex].
Въвеждаме функциите: [tex]\gamma (x)=\sum_{p\le x}log(p)[/tex] и [tex]\delta (x)=\sum_{p^{m}\le x}log(p)[/tex], където [tex]x>0[/tex] е произволно реално число.Tук под [tex]p[/tex], ще разбираме просто число, т.е. съответните суми са разспростряни само върху прости числа ненадминаващи дадено реално число [tex]x[/tex].
Например [tex]\gamma (10)=log(2)+log(3)+log(5)+log(7), \delta (12)=3log(2)+2log(3)+log(5)+log(7)+log(11)[/tex]. Разбира се [tex]\delta (x)=\sum_{p\le x}[\frac{log(x)}{log(p)}]log(p)[/tex], понеже при [tex]x\ge 1, p^{m}\le x<p^{m+1} [/tex], за някое естествено [tex]m [/tex]. Тогава да означим със [tex][y][/tex], цялата част на реалното число [tex]y[/tex]. Toгава [tex]m=[\frac{log(x)}{log(p)}][/tex]. Oт тук следва и представянето [tex]\delta (x)=\sum_{p\le x}[\frac{log(x)}{log(p)}]log(p)[/tex].

Сега ще докажем чрез индукция, че [tex]2) \gamma (n)<2n.log(2)[/tex], при [tex]n\ge 1[/tex].
Директно проверяваме верността на неравенството при [tex]n=1, n=2[/tex].Да предположим, че неравенството е в сила за някое [tex]n\ge 2[/tex]. Ясно е че [tex]\frac{N}{2}=\frac{(2n-1)!}{(n)!(n-1)!}[/tex]. Тогава, ако [tex]n<p\le 2n-1[/tex], то [tex]p[/tex] дели [tex]\frac{N}{2}[/tex], от където заключаваме, че [tex]\frac{N}{2}\ge p_{1}p_{2}...p_{s}[/tex], където [tex]p_{1}p_{2}...p_{s}[/tex] са всичките прости числа в интервала [tex](n,2n-1][/tex]. Логаритмуваме последното неравенство и получаваме: [tex]log(\frac{N}{2})\ge \gamma (2n-1)-\gamma (n)[/tex]. Логаритмувайки [tex]1)[/tex], получаваме [tex]log(N)<2nlog(2)-\frac{1}{2}log(2n)[/tex]. От тези 2 неравенства получаваме [tex]\gamma (2n-1)-\gamma (n)<(2n-1)log(2)-\frac{1}{2}log(2n)[/tex], но съгласно индукционното предположение [tex]\gamma (n)<2n.log(2)[/tex]. Следователно [tex]\gamma (2n-1)<(4n-1)log(2)-\frac{1}{2}log(2n)[/tex], откъдето следва, при [tex]n\ge 2[/tex] е в сила [tex]\gamma (2n-1)<2(2n-1)log(2)[/tex]. Накрая [tex]\gamma (2n)=\gamma (2n-1)<4n.log(2)[/tex].Индукционната стъпка е завършена и неравенството е доказано.

За да докажем Теоремата на Чебишев(Постулат на Бертран), достатъчно е да покажем, че [tex]\gamma (2n)-\gamma (n)\ge 0[/tex], за [tex]n\ge 64[/tex], и да проверим верността й за [tex]n\le 64[/tex].
Отново разглеждаме биномния коефициент [tex]N=\frac{(2n)!}{(n!)^{2}}=(p_{1})^{v_{p_{1}}}(p_{2})^{v_{p_{2}}}...(p_{t})^{v_{p_{t}}}[/tex],
където [tex]p_{1},p_{2},...,p_{t}[/tex] са всички прости числа по-малки от [tex]2n[/tex], а
[tex]v_{p}=\sum_{r\ge 1}([\frac{2n}{p^{r}}]-2[\frac{n}{p^{r}}])[/tex], където със [tex][y][/tex] сме означили цялата част на [tex]y[/tex]. Логаритмуваме равенството [tex]N=\frac{(2n)!}{(n!)^{2}}=(p_{1})^{v_{p_{1}}}(p_{2})^{v_{p_{2}}}...(p_{t})^{v_{p_{t}}}[/tex]
и получаваме:[tex]3) [/tex] [tex]log(N)=\sum_{p\le 2n}(v_{p}).log(p)[/tex].
Разделяме интервала [tex][1,2n][/tex] на четири под-интервала:
[tex] n<p\le 2n[/tex]
[tex] \frac{2n}{3}<p\le n[/tex]
[tex] \sqrt{2n}<p\le \frac{2n}{3}[/tex]
[tex]p\le \sqrt{2n}[/tex].
Ще пресметнем сумата в дясната страна на равенството [tex]log(N)=\sum_{p\le 2n}(v_{p}).log(p)=(\sum_{})_{1}+(\sum_{})_{2}+(\sum_{})_{3}+(\sum_{})_{4}[/tex], като пресмятанията ги извършаваме във всеки от четирите интервала.

1сл. [tex] n<p\le 2n[/tex].
Имаме [tex]\frac{n}{p}<1, 1\le \frac{2n}{p}<2[/tex], тогава [tex][\frac{n}{p}]=0,[\frac{2n}{p}]=1, [\frac{2n}{p^{2}}]=0[/tex].Следователно [tex]v_{p}=1[/tex], oттук [tex]\sum_{n<p\le 2n}(v_{p}).log(p)=(\sum_{})_{1}=\sum_{ n<p\le 2n}log(p)=\gamma (2n)-\gamma (n)[/tex].

2сл. [tex] \frac{2n}{3}<p\le n[/tex]
[tex]1\le \frac{n}{p}<\frac{3}{2}[/tex], и следователно
[tex][\frac{n}{p}]=1,[\frac{2n}{p}]=2,[\frac{2n}{p^{2}}]=0[/tex], тогава [tex](\sum_{})_{2}=0[/tex], при [tex]n\ge 3[/tex].

3сл. [tex] \sqrt{2n}<p\le \frac{2n}{3}[/tex]
Нека [tex]n\ge 5[/tex].
Тогава [tex]\frac{n}{p^{2}}<\frac{2n}{p^{2}}<1[/tex], следователно [tex]v_{p}=[\frac{2n}{p}]-2[\frac{n}{p}]=0, 1\le 1[/tex]. Заключаваме, че [tex](\sum_{})_{3}\le \sum_{\sqrt{2n}<p\le \frac{2n}{3}}log(p)=\gamma (\frac{2n}{3})-\gamma (\sqrt{2n})[/tex].
Но [tex]\gamma (sqrt{2n})=\sum_{p\le sqrt{2n}}log(p)\ge log(2)\sum_{p\le sqrt{2n}}1=log(2)\pi (sqrt{2n})[/tex], където с [tex]\pi (x)[/tex] сме означили броя на простите числа ненадминаващи реалното число [tex]x[/tex].
Окончателно получаваме, че [tex](\sum_{})_{3}\le \sum_{\sqrt{2n}<p\le \frac{2n}{3}}log(p)=\gamma (\frac{2n}{3})-\gamma (\sqrt{2n})\le \gamma (\frac{2n}{3})-log(2)\pi (\sqrt{2n})[/tex].

4сл. [tex]p\le \sqrt{2n}[/tex].
Не е трудно да се докаже неравенството:[tex]v_{p}=\sum_{r\ge 1}([\frac{2n}{p^{r}}]-2[\frac{n}{p^{r}}])\le [\frac{log(2n)}{log(p)}][/tex]. Тогава Тогава [tex](\sum_{})_{4}\le \sum_{p\le sqrt{2n}}[\frac{log(2n)}{log(p)}]log(p)\le \sum_{p\le sqrt{2n}}\frac{log(2n)}{log(p)}log(p)=log(2n).\pi (\sqrt{2n})[/tex].
Окончателно получихме, че [tex](\sum_{})_{4}\le log(2n).\pi (\sqrt{2n})[/tex].

Като обединим случаите 1,2,3,4 стигаме до неравенството: [tex]log(N)\le \gamma (2n)-\gamma (n)+\gamma (\frac{2n}{3})-(log(2)-log(2n)).\pi (\sqrt{2n})[/tex], от където получаваме: [tex]\gamma (2n)-\gamma (n)\ge log(N)-\gamma (\frac{2n}{3})-log(2n).\pi (\sqrt{2n})[/tex].

Въз основа на доказаните до този момент неща имаме (при [tex]n\ge 8[/tex]):
а) [tex]\gamma (\frac{2n}{3})=\gamma ([\frac{2n}{3}])<2\frac{2n}{3}.log(2)[/tex]
б) [tex]log(N)>2n.log(2)-log(2\sqrt{n})[/tex]
в) [tex]\pi (n)\le \frac{n}{2}[/tex]

Въз основа на последното неравенство и точките а),б),в) имаме:
[tex]\gamma (2n)-\gamma (n)>(\frac{2n}{3}-1)log(2)-\frac{\sqrt{2n}+1}{2}log(n)[/tex].
Лесно се показва, че функцията [tex]f(x)=(\frac{2x}{3}-1)log(2)-\frac{\sqrt{2x}+1}{2}log(x)[/tex] е растяща при [tex]x>2^{6}[/tex], и понеже [tex]f(2^{6})>0[/tex], то [tex]\gamma (2n)-\gamma (n)>0[/tex]. Значи при [tex]n\ge 64[/tex] - твърдението е доказано.
Остана да се провери верността на твърдението в интервала [tex](1,64][/tex]. Разглеждаме редицата [tex]2,3,5,7,13,23,43,67[/tex].С това проверката е завършена и твърдението- доказано.


Последната промяна е направена от Мирослав Стоенчев на Mon Dec 03, 2007 4:47 pm; мнението е било променяно общо 1 път
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Мирослав Стоенчев
Напреднал


Регистриран на: 21 Aug 2007
Мнения: 279

Репутация: 72
гласове: 45

МнениеПуснато на: Sun Dec 09, 2007 12:32 pm    Заглавие:

Теорема за функцията [tex][x].[/tex] Ако [tex]n[/tex] е естествено число а [tex]p[/tex]-просто, то степента с която [tex]p[/tex] участва в каноничното разлагане на [tex]n!=1.2...n[/tex] на прости множители е равна на [tex]\alpha =\sum_{i=1}^{\infty}[\frac{n}{p^{i}}].[/tex]

Д-во:Ще отбелижим, че горепосочената сума е крайна, т.е. съществува такова [tex]s\in N : p^{s}\le n<p^{s+1}.[/tex] Тогава [tex]\alpha =\sum_{i=1}^{s}[\frac{n}{p^{i}}].[/tex]

Вече отбелязахме, че съществува такова [tex]s\in N : p^{s}\le n<p^{s+1}.[/tex]
Дa означим с [tex]t_{i}[/tex] броя числата ненадминаващи [tex]n,[/tex] които се делят на [tex]p^{i},[/tex] но не се делят на [tex]p^{i+1}.[/tex] Съобразяваме, че [tex]\alpha =1.t_{1}+2t_{2}+...+st_{s}[/tex] [tex]t_{1}=[\frac{n}{p}]-[\frac{n}{p^{2}}],...,t_{k}=[\frac{n}{p^{k}}]-[\frac{n}{p^{k+1}}],...,t_{s}=[\frac{n}{p^{s}}]-[\frac{n}{p^{s+1}}].[/tex]
Тогава [tex]\alpha =1.t_{1}+2t_{2}+...+st_{s}=\sum_{i=1}^{s}i.t_{i}=\sum_{i=1}^{s}i([\frac{n}{p^{i}}]-[\frac{n}{p^{i+1}}])=\sum_{i=1}^{s}i([\frac{n}{p^{i}}])-\sum_{i=1}^{s}i([\frac{n}{p^{i+1}}])=\sum_{i=1}^{s}i([\frac{n}{p^{i}}])-\sum_{i=1}^{s}(i+1)([\frac{n}{p^{i+1}}])+\sum_{i=1}^{s}([\frac{n}{p^{i+1}}])[/tex]
Toгава [tex]\alpha =\sum_{i=1}^{s}[\frac{n}{p^{i}}],[/tex] с което теоремата е доказана.


Теорема на Уилсон. Едно естествено число [tex]p>1[/tex] е просто, тогава и само тогава, когато е изпълнено сравнението [tex](p-1)!+1\equiv 0(mod (p)).[/tex]

Д-во:Нека [tex]p[/tex] е просто число.
От малката теорема на Ферма имаме, че [tex]x^{p-1}-1\equiv 0(mod(p)),[/tex] при [tex]x=1,2,...,p.[/tex] Следователно конгруенцията [tex]x^{p-1}-1\equiv (x-1)(x-2)...(x-p+1)(mod(p))[/tex] е тъждествено вярна. Полагаме [tex]x=p \Rightarrow p^{p-1}-1\equiv (p-1)(p-2)...(p-p+1)(mod(p))\Leftrightarrow -1\equiv (p-1)!(mod(p)).[/tex]

Нека сега е в сила [tex](p-1)!+1\equiv 0(mod(p)).[/tex] Ще докажем, че [tex]p[/tex] е просто.Да допуснем, че [tex]p[/tex] е съставно. Toгава съществува просто число [tex]q:[/tex] [tex]q<p[/tex]. Следователно [tex]q|(p-1)![/tex] Също така [tex]q|p, p|(p-1)!+1\Rightarrow q|(p-1)!+1[/tex] Получихме, че [tex]q|(p-1)!, q|(p-1)!+1,[/tex] което е невъзможно, поради [tex]gcd((p-1)!,1+(p-1)!)=1.[/tex] Теоремата е доказана.


Следствие. Ако [tex]p\equiv 1(mod(4)),[/tex] то [tex]\exists x:[/tex] [tex] x^{2}\equiv -1(mod(p)).[/tex] Ако [tex]p\equiv 3(mod(4)),[/tex] то сравнениято [tex]x^{2}\equiv -1(mod(p))[/tex] няма решение.

Д-во:Нека [tex]p[/tex] е нечетно просто число. Полагаме [tex]q=\frac{p-1}{2}.[/tex]
При [tex]i=1,2,...,q\Rightarrow q+i\equiv i-q-1(mod(p)).[/tex] Следователно [tex]-1\equiv (p-1)!=1.2...(\frac{p-1}{2}).(\frac{p-1}{2}+1)...(\frac{p-1}{2}+\frac{p-1}{2})\equiv(\frac{p-1}{2})!\prod_{i=1}^{q}(i-\frac{p-1}{2}-1)\equiv (\frac{p-1}{2})!\prod_{i=1}^{q}(-i)\equiv ((\frac{p-1}{2})!)^{2}(-1)^{q}(mod(p)) [/tex]
Tака получихме, че [tex]-1\equiv ((\frac{p-1}{2})!)^{2}(-1)^{q}(mod(p))\Leftrightarrow ((\frac{p-1}{2})!)^{2}\equiv (-1)^{q+1}(mod(p)) [/tex]
1сл. Ако [tex]p\equiv 1(mod(4)),[/tex] т.е. [tex]p=4k+1,[/tex] то полагайки [tex]x=\pm((\frac{p-1}{2})!)^{2}\Rightarrow ((\frac{p-1}{2})!)^{2}\equiv (-1)^{q+1}\equiv (-1)^{2k+1}\equiv -1(mod(p))\Leftrightarrow x^{2}\equiv -1(mod(p)) [/tex] има решение.
2сл. Ако [tex]p\equiv 3(mod(4)),[/tex] т.е. [tex]p=4k+3,[/tex] то допускайки, че [tex]\exists x: [/tex] [tex] x^{2}\equiv -1(mod(p)) \Rightarrow (x^{2})^{\frac{p-1}{2}}\equiv (-1)^{\frac{p-1}{2}}\Rightarrow x^{p-1}\equiv (-1)^{2k+1}\equiv -1(mod(p))[/tex] Но съгласно малката теорема на Ферма имаме, че [tex]x^{p-1}\equiv 1(mod(p)) \Rightarrow 1\equiv x^{p-1}\equiv -1\Leftrightarrow 2\equiv 0(mod(p))\Leftrightarrow p=2,[/tex] което е противоречие. Следствието е доказано.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Мирослав Стоенчев
Напреднал


Регистриран на: 21 Aug 2007
Мнения: 279

Репутация: 72
гласове: 45

МнениеПуснато на: Sun Dec 16, 2007 7:42 pm    Заглавие:

Показател на цяло число по модул [tex]n[/tex]

Нека [tex]n>1[/tex] е естествено и [tex]a\in Z[/tex] е такова, че [tex]\gcd(a,n)=1.[/tex]
Разглеждаме редицата [tex]a,a^{2},a^{3},a^{4},...[/tex] В нея със сигурност има числа, които да са сравними с [tex]1(mod(n)),[/tex] тъй като съгласно теоремата на Ойлер [tex]a^{\varphi(n)}\equiv 1(mod(n)).[/tex] Да означим с [tex]\delta[/tex] най-малкото естествено число такова, че [tex]a^{\delta}\equiv 1(\bmod n).[/tex] Числото [tex]\delta[/tex]
ще наричаме показател на [tex]a[/tex] по модул [tex]n.[/tex]

Теорема. Нека [tex]n>1[/tex] е естествено и [tex]a\in Z[/tex] е такова, че [tex]\gcd(a,n)=1.[/tex] Нека още [tex]\delta[/tex] е показателя на [tex]a[/tex] по модул [tex]n.[/tex] Тогава числата [tex]a,a^{2},...,a^{\delta}[/tex] са две по две несравними по модул [tex]n.[/tex] Освен това, ako [tex]a^{m}\equiv 1(\bmod n),[/tex] то [tex]\delta|m.[/tex]

Д-во: Имаме [tex]a^{m}\equiv 1(\bmod n)[/tex] и [tex]a^{\delta}\equiv 1(\bmod n).[/tex] Да разделим с частно и остатък [tex]m=t.\delta+r;0\le r\le \delta-1.[/tex] Тогава [tex]1\equiv a^{m}=a^{t.\delta+r}=a^{r}(a^{\delta})^t\equiv a^{r}.1\equiv a^{r}\Rightarrow a^{r}\equiv 1(\bmod n).[/tex] Но [tex]0\le r\le \delta-1,[/tex] което е възможно само при [tex]r=0\Rightarrow \delta|m.[/tex]

Класове остатъци и система остатъци по модул [tex]n[/tex]

Дефиниция. Пълна система остатъци по модул [tex]n[/tex] - [tex]0,1,2,...,n-1.[/tex] Казваме, че естествените числа [tex]a,b[/tex] принадлежат на един и същи клас по модул [tex]n,[/tex] ако [tex]a\equiv b(\bmod n).[/tex]

Теорема. Ако естествените числа [tex]m,n[/tex] са взаимно прости, а [tex]r\in Z,[/tex] то
числата [tex]r,m+r,2m+r,...,(n-1)m+r[/tex] образуват пълна система остатъци по модул [tex]n.[/tex]
Д-во: Ще докажем, че числата са 2 по 2 несравними по модул [tex]n.[/tex] Наистина, нека [tex]0\le a<b\le n-1.[/tex] Тогава [tex]am+r\equiv bm+r(\bmod n)\Rightarrow (a-b)m\equiv 0(\bmod n)\Rightarrow (a-b)\equiv 0(\bmod n),[/tex] което е невъзможно поради [tex]0<|a-b|\le n-1.[/tex] Теоремата е доказана.

Теорема. Ако естествените числа [tex]m,n[/tex] са взаимно прости, а [tex]x,y[/tex] пробягват пълна система остатъци съответно по модул [tex]n[/tex] и [tex]m,[/tex] то числата от множеството [tex]\left\{mx+ny|x=0,1,2,...,n-1;y=0,1,2,...,m-1\right\}[/tex] образуват пълна система остатъци по модул [tex]mn.[/tex]
Д-во:Ще докажем, че числата от множеството [tex]\left\{mx+ny|x=0,1,2,...,n-1;y=0,1,2,...,m-1\right\}[/tex] са 2 по 2 несравними по модул [tex]m.n,[/tex] и тъй като са [tex]m.n[/tex] на брой, то те ще образуват пълна система остатъци по модул [tex]mn.[/tex]
Наистинa, ako [tex]mx_{1}+ny_{1}\equiv mx_{2}+ny_{2}(\bmod mn)\Leftrightarrow m(x_{1}-x_{2})+n(y_{2}-y_{1})\equiv 0(\bmod mn)\Leftrightarrow m|(y_{2}-y_{1}); n|(x_{1}-x_{2}).[/tex] Последното е невъзможно, тъй като [tex]0<|y_{2}-y_{1}|\le m-1, 0<|x_{1}-x_{2}|\le n-1.[/tex]

Теорема. (Китайска теорема за остатъците) Нека [tex]m_{1},m_{2},...,m_{k}[/tex] са две по две взаимно-прости естествени числа, а [tex]n_{1},n_{2},...,n_{k}[/tex] са произволни цели числа.Тогава съществува цяло число [tex]x\in Z[/tex] такова, че [tex]x\equiv n_{i}(\bmod m_{i}), i=1,2,...,k.[/tex]
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
zhivko_sh
Начинаещ


Регистриран на: 22 Feb 2008
Мнения: 37

Репутация: 20.5Репутация: 20.5
гласове: 12

МнениеПуснато на: Mon Sep 22, 2008 9:05 am    Заглавие: Теорема на Чебишов

В сила е дори фактът, че при n>5 между n и 2n има поне ДВЕ прости числа и в тази връзка постулатът на Бертран следва директно от теоремата на Чебишов. Wink
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
sd_pld
Начинаещ


Регистриран на: 05 Dec 2006
Мнения: 68

Репутация: 12.9
гласове: 1

МнениеПуснато на: Wed Sep 24, 2008 3:51 pm    Заглавие:

В сила е ,дори фактът ,че ако n>2k,,то измежду числата n,(n-1)....(n-k) има просто число,което е еквивалентно с твърдението ,че n над k има прост делител ,който е по-голям от к
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Baronov
Напреднал


Регистриран на: 05 Jun 2008
Мнения: 316

Репутация: 55.4
гласове: 39

МнениеПуснато на: Wed Sep 24, 2008 4:01 pm    Заглавие:

sd_pld написа:
В сила е ,дори фактът ,че ако n>2k,,то измежду числата n,(n-1)....(n-k) има просто число,което е еквивалентно с твърдението ,че n над k има прост делител ,който е по-голям от к


Двете твърдения, които си написал далеч не са еквивалентни. Нещо повече, първото съвсем не е в сила. Вземи си к=1. Тогава, според теб, от всеки 2 последователни естествени числа едното трябва да е просто.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Покажи мнения от преди:   
   Форум за математика Форуми -> Теория свързана с олимпиади Часовете са според зоната GMT + 2 Часа
Страница 1 от 1

 
Идете на:  
Не Можете да пускате нови теми
Не Можете да отговаряте на темите
Не Можете да променяте съобщенията си
Не Можете да изтривате съобщенията си
Не Можете да гласувате в анкети
You cannot attach files in this forum
Може да сваляте файлове от този форум
Copyright © 2005-2015 math10.com.