Algebra 2-02 arytmetyka liczb całkowitych.pdf

Wykład2

Naostatnimwykładzieudowodnili±mynast¦puj¡cetwierdzenie:

Twierdzenie1 Je±lia,b 2 Z ia 6 =0 lubb 6 =0 .toistniej¡liczbycałkowite

u,v,»eau + bv = NWD ( a,b ) .

Mo»napostawi¢ogólnepytaniedlajakich a,b,c 2 Zrównanie ax + by = c

marozwi¡zaniecałkowite?Powy»szetwierdzeniemówi,»etakierozwi¡zanie

istniejeje±li c =NWD( a,b ).Czytylkowtakimprzypadku?Okazujesi¦,

»enie,bozfaktuistnieniarozwi¡zaniarównania ax + by =NWD( a,b ),

wynikaistnienierozwi¡zaniarównania ax + by = k NWD( a,b ).Czylije±li

NWD( a,b ) | c torównanie ax + by = c marozwi¡zanie.Inietrudnozauwa»y¢,

»eje±liNWD( a,b )- c to ax + by = c niemo»emie¢rozwi¡zaniacałkowitego

(prawastronajestpodzielnaprzezNWD( a,b ),alewanie).Udowodnili±my

wi¦c:

Twierdzenie2 Je±lia,b,c 2 Z torównanieax + by = cmarozwi¡zanie

całkowitewtedyitylkowtedygdyNWD ( a,b ) | c.

ZTwierdzenia1mo»nawysnu¢nast¦puj¡cyWniosek:

Wniosek1 Liczbadjestnajwi¦kszymwspólnymdzielnikiemliczbaibwtedy

itylkowtedygdy

(i) d | aid | b,

(ii) je±lic | aic | btoc | d

Dowód

( ) )Niech d =NWD( a,b )wtedyzgodniezpowy»szymtwierdzeniemistniej¡

liczbycałkowite u i v takie,»e d = ua + vb .Je±liliczba c | a i c | b to a = kc,b = lc

dlapewnych k,l .St¡d d = ukc + vlc =( uk + vl ) c ,awi¦c c | d .

( ( )Je±li c | d to c ¬ d awi¦cpunkty(i),(ii)poci¡gaj¡warunki:

(i) d | a i d | b ,

(ii)je±li c | a i c | b to c ¬ d

którestanowi¡deﬁnicj¦najwi¦kszegowspólnegodzielnika.

Liczby a i b nazywamy wzgl¦dniepierwszymi je±liNWD( a,b )=1.

Twierdzenie3 Liczbyaibs¡wzgl¦dniepierwszewtedyitylkowtedygdy

istniej¡liczbycałkowiteuiv,»eau + bv =1 .

Dowód Je±liNWD( a,b )=1tozgodniezTwierdzeniem1istniej¡ u,v takie,

»e au + bv =1,aje±lidlapewnych u,v 2 Zmamy au + bv =1toNWD( a,b ) | 1,

awi¦cNWD( a,b )=1.

Twierdzenie4 Je±lia | bciliczbya,bs¡wzgl¦dniepierwszetoa | c.

Dowód Poniewa»NWD( a,b )=1tozgodniezpowy»szymTwierdzeniem

istniej¡liczby u,v takie,»e ua + vb =1.Mno»¡ctorównanieobustronnie

przez c mamy uac + vbc = c .Poniewa» a | bc toistnieje k ,»e bc = ka ,awi¦c

uac + vka = c .St¡d( uc + vk ) a = c ,wi¦c a | c .

B¦dziemymówi¢,»eliczbacałkowita p jest pierwsza je±li p 6 =0 , ± 1i

jedynymidzielnikamiliczby p s¡ ± 1 , ± p .

Twierdzenie5 Liczbapjestpierwszawtedyitylkowtedygdypspełnia

warunek:je±lip | bctop | blubp | c.

Dowód

( ) )Załó»my,»e p jestliczb¡pierwsz¡i p | bc .Najwi¦kszywspólnydzielnik

liczb p i b jestrówny1lub p .Je±liNWD( p,b )= p to p | b .Wprzeciwnym

przypadkumamyNWD( p,b )=1izpoprzedniegoTwierdzenia p | c .

( ( )Przypu±¢my,»e p = kl wtedy p | kl ,awi¦c p | k lub p | l .Je±li p | k to

istnieje t ,»e k = pt ,awi¦c p = ptl czyli tl =1,atarówno±¢wzbiorze

liczbcałkowitychjestmo»liwatylkodla l = ± 1.Tooznacza,»e p niema

dzielnikówpoza ± 1 , ± p ,awi¦cjestliczb¡pierwsz¡.

Twierdzenietomo»narozszerzy¢wnast¦puj¡cysposób:

Wniosek2 Je±lip | a 1 a 2 ··· a n topdzieliprzynajmniejjednoa i .

Twierdzenie6 Ka»daliczbacałkowitanopróczliczb 0 , ± 1 jestiloczynem

liczbpierwszych.

Dowód Twierdzeniewystarczyudowodni¢wprzypadkugdy n> 1.Przy-

pu±¢my,»eistniej¡liczbynaturalne > 1,którenies¡iloczynamiliczbpierw-

szych.Oznaczmyprzez S zbiórtakichliczb.Wtedyistniejenajmniejszaliczba

wzbiorze S (napodstawieADP).Nazwijmyj¡ s .Taliczbaniejestpierwsza,

awi¦cistniej¡liczby a,b ,takie»e s = ab i1 <a<s, 1 <b<s .St¡d

wynika,»e a,b 6 = S .Zatemliczby a,b dadz¡si¦zapisa¢jakoiloczynyliczb

pierwszych,awi¦c s równie»cojestsprzecznezzało»eniem»etegosi¦nie

dazrobi¢.Czyli S jestzbiorempustym.

Twierdzenie7(ZasadniczeTwierdzenieArytmetyki) Ka»daliczbacał-

kowita,ró»naod 0 , ± 1 jestiloczynemliczbpierwszych.Rozkładnaliczby

pierwszejestjednoznacznywnast¦puj¡cymsensie:Je±li

n = p 1 p 2 ··· p r in = q 1 q 2 ··· q s

gdziep i ,q j s¡pierwszetos = rije±lip 1 ¬ p 2 ¬ ... ¬ p r ,q 1 ¬ q 2 ¬ ... ¬ q s

p 1 = ± q 1 ,p 2 = ± q 2 ,...,p r = ± q r

Dowód Mo»liwo±¢rozkładuwynikazpoprzedniegoTwierdzenia.przypu±¢-

myteraz,»e:

p 1 p 2 ··· p r = q 1 q 2 ··· q s

wtedy p 1 | q 1 q 2 ··· q s ,awi¦cdlapewnego i mamy p 1 | q i iponiewa» q i jestpierw-

szato q i = ± p 1 ,awi¦cpoprzenumerowaniuotrzymamy p 1 = ± q 1 itd...

Nast¦puj¡ceTwierdzeniepozwalaupro±ci¢poszukiwaniedzielnikówpierw-

szychdanejliczby.

Twierdzenie8 Je±lilic zba n> 1 niejestpierwszatonposiadadzielnik

Oznaczmyprze ( n )ilo±¢dodatnichliczbpierwszychmniejszychb¡d¹

równychod n .Wtedywrazzewzrostem n liczba ( n )zbli»asi¦do ln n n ,czyli

mamy:

( n )

lim

n !1

ln n =1

mniejszyb¡d¹równyod p n.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: