Teoria liczb - definicje i twierdzenia.pdf - Matematyka . Powtórzenia. Przykłady - heroinka94

Wybranepojƒciaitwierdzeniazwyk“aduzteoriiliczb

1.Podzielno–¢

Przedmiotembada«teoriiliczbs¡w“asno–ciliczbca“kowitych.

Zbi ó rliczbca“kowitychoznacza¢bƒdziemysymbolemZ:

Zbi ó rliczbnaturalnychoznacza¢bƒdziemysymbolemN:

Zasadaminimum.Je–lizbi ó rXjestniepustympodzbioremzbioruliczbnaturalnych,

towzbiorzeXistniejeliczbanajmniejsza.

De nicja.Liczbaca“kowitabjestpodzielnaprzezliczbƒca“kowit¡a(a 6=0);je–li

istniejetakaliczbaca“kowitak,»eb=ka:

Piszemywtedya j b iczytamy:

(i) adzielib;

(ii)ajestpodzielnikiemb;

(iii)bjestpodzielnaprzeza:

Je–liliczbaca“kowitabniejestpodzielnaprzezliczbƒca“kowit¡a;topiszemya-b:

Twierdzenie.Niecha;b;c;m 2Z;przyczyma;m 6=0:

(1)Je–lia j b,toa j bc:

(2)Je–lia j bib j c;toa j c;(b 6=0):

(3)Je–lia j bia j c;toa j(bx+cy)dladowolnychx;y 2Z:

(4)Je–lia j bib j a,tojaj=jbj(b 6=0):

(5)Je–lia j bia >0; b >0;toa b:

(6)a j bwtedyitylkowtedygdyma j mb.

Twierdzenie.Dladowolnejliczbyca“kowitej bidowolnejliczbyca“kowitej a 6=0,

istniej¡liczbyca“kowitekir,takie,»e

b=ka+r; 0 r < jaj:

Je–lia-b;tozachodzinier ó wno–¢ostra.

Liczbƒrnazywamyreszt¡zdzielenialiczbybprzezliczbƒa:

De nicjanajwiƒkszegowsp ó lnegodzielnika.Liczbƒa 2Znf0gnazywamywsp ó lnym

dzielnikiemliczbca“kowitychbic,je–lia j bia j c:Je–liprzynajmniejjednasposr ó d

liczbbicjestr ó »naodzera,tow–r ó dwsp ó lnychdzielnik ó wliczbb;c(kt ó rychjest

sko«czeniewiele)istniejenajwiƒkszy.Tennajwiƒkszyspo–r ó dwsp ó lnychdzielnik ó wliczb

b,cnazywamynajwiƒkszymwsp ó lnymdzielnikiemliczbbic.

Najwiƒkszywsp ó lnydzielnikliczbbicoznaczamysymbolem(b;c)lubNwd(b;c):

Wpodobnyspos ó bde niujemynajwiƒkszywsp ó lnydzielnikliczbca“kowitychb 1 ;b 2 ;:::b n

zkt ó rychprzynajmniejjednajestr ó »naodzera.Dzielniktenoznaczamysymbolem

(b 1 ;b 2 ;:::b n ):

Twierdzenie.Je–lig=(b;c)jestnajwiƒkszymwsp ó lnymdzielnikiemliczbca“kowitych

bic,toistniej¡liczbyca“kowitex 0 ;y 0 takie,»e

g=bx 0 +cy 0 :

Innymis“owy:najwiƒkszywsp ó lnydzielnikliczbca“kowitychbicjestkombinacj¡

liniow¡tychliczbowsp ó “czynikachca“kowitych.

Twierdzenie.Najwiƒkszywsp ó lnydzielnikliczbca“kowitychbicmo»eby¢scharak-

teryzowanywnastƒpuj¡cysposob:

(1)Jakonajmniejszaliczbanaturalnanale»¡cadozbioru

A=fbx+cy:x;y 2Zg:

(2)Jakowsp ó lnynaturalnydzielnikliczbbicpodzielnyprzezka»dyinnywsp ó lny

dzielniktychliczb.

Twierdzenie(AlgorytmEuklidesa).Niechbicbƒd¡dwiemaliczbamica“kowitymi,

przyczymc >0:Najwiƒkszywsp ó lnydzielnikliczbbicmo»eby¢obliczonyprzypomocy

seriir ó wno–ci:

0< r 1 < c;

0< r 2 < r 1 ;

0< r 3 < r 2 ;

0< r 4 < r 3 ;

. . .

0< r j < r j1 ;

b = k 1 c +r 1 ;

c = k 2 r 1 +r 2 ;

r 1 = k 3 r 2 +r 3 ;

r 2 =k 4 r 3 +r 4 ;

. . .

r j2 =k j r j1 +r j ;

r j1 =k j+1 r j :

Ostatniaresztar j jestnajwiƒkszymwsp ó lnymdzielnikiemliczbbic:

Przyk“ad.Niechb=3102,c=1044:AlgorytmEuklidesadajenamr ó wno–ci

3102=21044+1014;

1044=11014+30;

1014=3330+24;

30=124+6;

24=46:

Ostatniaresztajestr ó wna6:Zatem(3102;1044)=6:

Zpoprzednichr ó wno–ciotrzymujemykolejno

6=30124=30(10143330)=34301014=

=34(10441014)1014=341044351014=

=34104435(310221044)=(35)3102+1041044:

St¡d

(3102;1044)=(35)3102+1041044:

Zatemnajwiƒkszywsp ó lnydzielnikliczb3102i1044jestkombinacj¡liniow¡tychliczbo

wsp ó “czynnikachodpowiedniox 0 =35iy 0 =104:

De nicjanajmniejszejwsp ó lnejwielokrotno–ci.Niecha 1 ;a 2 ;:::;a n bƒd¡liczbami

ca“kowitymir ó znymiodzera.Powiemy,»eliczbaca“kowitabjestwsp ó ln¡wielokrotno–-

ci¡liczba 1 ;a 2 ;:::;a n ,je–lia i j bdlaka»degoi 2f1;2;:::;ng:Najmniejszazewsp ó lnych

wielokrotno–cidodatnichliczba 1 ;a 2 ;:::;a n nazywasiƒnajmniejsz¡wsp ó ln¡wielokrotno–-

ci¡tychliczb.

Najmniejsz¡wsp ó ln¡wielokrotno–¢liczba 1 ;a 2 ;:::;a n oznaczamysymbolem[a 1 ;a 2 ;:::;a n ]

lubNww(a 1 ;a 2 ;:::;a n ):

Twierdzenie.Ka»dawsp ó lnawielokrotno–¢liczbca“kowitychr ó »nychodzeraa 1 ;a 2 ;:::;a n

jestpodzielnaprzezichnajmniejsz¡wsp ó ln¡wielokrotno–¢[a 1 ;a 2 ;:::;a n ]:

Twierdzenie.Iloczynnajwiƒkszegowsp ó lnegodzielnikadw ó chliczbnaturalnychiich

najmniejszejwsp ó lnejwielokrotno–cijestr ó wnyiloczynowitychliczb.Czyli

(a;b)[a;b]=ab; a;b 2N:

Przyk“ad.Obliczy¢najmniejsz¡wsp ó ln¡wielokrotno–¢liczb3102i1044:

Rozwi¡zanie

(3102;1044)=6.Zatemnamocypowy»szegotwierdzenia

[3102;1044]= 31021044

6 =539748:

2.R ó wnanianieoznaczone

Twierdzenie.Niecha 1 ;a 2 ;:::;a n ;bbƒd¡liczbamica“kowitymizkt ó rychprzynajmniej

jednaliczbaa i jestr ó »naodzera(i 2f1;2;:::;ng).

Natobyr ó wnaniepostaci

a 1 x 1 +a 2 x 2 +:::+a n x n =b

mia“orozwi¡zaniewliczbachca“kowitychpotrzebaiwystarcza,bynajwiƒkszywsp ó lny

dzielnikliczba 1 ;a 2 ;:::;a n dzieli“liczbƒb:

De nicjaliczbwzglƒdniepierwszych.Liczbyca“kowitea;bnazywamyliczbamiwzglƒd-

niepierwszymi,je–li(a;b)=1:

Twierdzenie.Natobyr ó wnaniepostaci

ax+by=c; a;b;c 2Z; a 2 +b 2 >0;

mia“orozwi¡zaniewliczbachca“kowitychpotrzebaiwystarcza,by(a;b)j c:

Spostrze»enie.Niechbƒdziedaner ó wnaniepostaci

ax+by=1; a;b 2Z; a 2 +b 2 >0:

()

Je–liliczbyca“kowitea;bs¡wzglƒdniepierwsze,tor ó wnanie()posiadarozwi¡zaniew

liczbachca“kowitych.

Twierdzenie.Je–liparaliczbca“kowitych(x 0 ;y 0 )jestpewnymrozwi¡zaniemr ó wnania

ax+by=c; a;b;c 2Z; a 2 +b 2 >0;

towszystkierozwi¡zaniategor ó wnaniawliczbachca“kowitychotrzymujemyzewzoru

x=x 0 + b

(a;b) t; y=y 0 a

(a;b) t; t 2Z:

Przyk“ad.R ó wnanie

()

435x+2012y=6

rozwi¡za¢wliczbachca“kowitych.

Rozwi¡zanie

Najwiƒkszywsp ó lnydzielnikliczb435i2112jestr ó wny3:R ó wnanie()marozwi¡zanie,

gdy»3j12:Ponadto“atwoobliczy¢,»e

() 435(335)+211269=(435;2012)=3:

Mno»¡cobiestronyr ó wno–ci()przez2otrzymujemy

435(3352)+2112(692)=32=6:

Czyli

435(670)+2112138=6:

Znale„li–myzatemrozwi¡zanieszczeg ó lner ó wnania()x 0 =670,y 0 =138:

Zgodniezpowy»szymtwierdzeniemrozwi¡zanie,r ó wnania()maposta¢

x=670+704t; y=138+145t; t 2Z:

3.Liczbypierwsze

De nicjaliczbpierwszych.Je–lipozadzielnikamitrywialnymiliczbanaturalnan;

wiƒkszaodjedno–ci,nieposiadainnychdzielnik ó wnaturalnych,tonazywamyj¡liczb¡

pierwsz¡.

Dok“adniej:liczba n 2Nnf1g jestliczb¡pierwsz¡,je–lijedynymijejdzielnikami

naturalnymis¡liczba1orazliczban:

Twierdzenie.(Zasadniczetwierdzeniearytmetyki).Niecha;b;cbƒd¡dowolnymiliczbami

naturalnymi.Je–li(a;b)=1ia j bc;toa j c:

Twierdzenie.(Podstawowetwierdzeniearytmetyki)Ka»daliczbanaturalnanwiƒksza

odjedno–cidajesiƒprzedstawi¢jednoznacznie,zdok“adno–ci¡dokolejno–ciczynnik ó w,

wpostaciiloczynuliczbpierwszych.Toznaczy,»egdydanes¡dwarozk“ady

n=p 1 p 2 :::p k ;oraz n=q 1 q 2 :::q l

tejsamejliczbynaturalnejnnaczynnikipierwsze,tok=limo»naliczbyp j iq s (j 2

f1;2;:::;kg,s 2 f1;2;:::;lg);takuporz¡dkowa¢,byodpowiadaj¡cesobieczynnikiby“y

r ó wne.

Twierdzenie.Ka»daliczbaz“o»onanmadzielnikpierwszymniejszylubr ó wny p n:

Powy»szetwierdzeniejestr ó wnowa»netwierdzeniu

Twierdzenie.Je–liliczb a naturalnan >1niejestpodzielnaprzez»adn¡liczbƒpier-

wsz¡mniejsz¡lubr ó wn¡

p n,tojestliczb¡pierwsz¡.

SitoEratostenesa(276-194).We„mypoduwagƒci¡gliczbnaturalnych

( 1 ) 2;3;4;5;6;7;8;9;10;11;12;13;14;15;16;17;18;19;::::

Usu«myznaszegoci¡gu( 1 )wszystkieliczbywiƒkszeodpierwszejliczbypierwszej p 1 =2

ipodzielneprzez2:Otrzymujemyci¡g

( 2 ) 2;3;5;7;9;11;13;15;17;19;::::

Pierwsz¡nieusuniƒt¡liczb¡wiƒksz¡od2jestliczbapierwszap 2 =3:Usuwamyterazz

naszegoci¡guwszystkieliczbywiƒkszeod3bƒd¡cewielokrotno–ciamiliczby3:Otrzymu-

jemyci¡g

( 3 )

2;3;5;7;11;13;17;19;::::

Pierwsz¡nieusuniƒt¡liczb¡niepodzieln¡przez2i3jestliczbapierwszap 3 =5:

Postƒpowaniekontynuujemyizan-tymrazemotrzymujemyn-t¡liczbƒpierwsz¡ p n :

Nastƒpnieusuwamyznaszegoci¡guwszystkieliczbywiƒkszeodp n bƒd¡cewielokrotno-

–ciamiliczbyp n :Pierwsz¡nieusuniƒt¡liczb¡jestliczbapierwszap n+1 :

Je–lici¡gjestsko«czonypostaci

() 2;3;4;5:::;N;

topostƒpowaniemo»emyzako«czy¢pootrzymaniunajwiƒkszejliczbypierwszej p k p

Wszystkieliczbypozosta“ewci¡gu()wiƒkszeodliczbyp k s¡liczbamipierwszymi.

Przyk“ad.We„mypoduwagƒci¡gliczbnaturalnych

() (2;3;4;5;6;7;8;9;10;11;12;13;14;15;16;17;:::;83;84;85):

Teoria liczb - definicje i twierdzenia.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: