Algebra 2-01 arytmetyka liczb całkowitych.pdf

Wykład1

Arytmetykaliczbcałkowitych

Napocz¡tkuzajmowa¢si¦b¦dziemyzbioremliczbcałkowitych

Z= { 0 , ± 1 , ± 2 ,... } .

Zakładamy,»eczytelnikznarelacj¦ < ,któraporz¡dkujetenzbiór.Zakłada-

myrównie»:

Aksjomatdobregoporz¡dku Ka»dyniepustyzbiórzło»onyzliczbcałko-

witychnieujemnychposiadaelementnajmniejszy

Oczywi±ciewcałymzbiorzeliczbcałkowitychpowy»szyaksjomatniejest

spełniony(niemanajmniejszejliczbycałkowitej).

Jakwiemyka»d¡liczb¦całkowit¡dodatni¡mo»napodzieli¢przezinn¡

liczb¦dodatni¡zreszt¡.Ide¦dzieleniazreszt¡wyja±nianast¦puj¡cetwier-

dzenie.

Twierdzenie1 ( Algorytmdzielenia )Niecha,bb¦d¡liczbamicałkowitymi.

Wtedyistniejedokładniejednaparaliczbcałkwitychq,r,taka»e

a = qb + ri 0 ¬ r<b

Dowód Rozwa»myzbiór S wszystkichliczbpostaci a − bx ,gdzie x jest

dowoln¡liczb¡całkowit¡,awi¦c

S = { a − bx | x 2 Z }

S 0 = { s 2 S | s 0 }

Zgodniezaksjomatemdobregoporz¡dkuistnienajmniejszaliczbazawarta

wzbiorze S 0 .Oznaczmyt¡liczb¦przez r ,awi¦c

r =min( S 0 )

Oznaczato,»eistnieje q ,takie»e r = a − qb i r 0.Poka»emy,»e r<b .

Niechbowiem r b ,wtedy r − b 0i r − b<r (bo b> 0)imamy

r − b = a − qb − b = a − ( q +1) b

Nietrudnojestzauwa»y¢,»ewzbiorze S istniej¡liczbynieujemne.Niechwi¦c

S 0 b¦dziepodzbioremzbioru S zło»onymzwszystkichliczbnieujemnych.

Mamywi¦c:

Tooznacza,»e r − b 2 S 0 i r − b jestmniejszeod r ,któryjestminimalnym

elementemwzbiorze S 0 ,awi¦cotrzymujemysprzeczno±¢.Sprzeczno±¢ta

wynikłazzało»enia,»e r b .Zatemmusimyby¢ r<b .Todajenamrozkład

postaci a = qb + r ,gdzie0 ¬ r<b .Teraztrzebapokaza¢jednoznaczno±¢

rozkładu.Przypu±¢my,»eistniej¡dwieró»neliczby r i r 0 ,takie»e a = qb + r

i a = q 0 b + r 0 i0 ¬ r<b ,0 ¬ r 0 <b .Wtedymamy r>r 0 lub r<r 0 .

Wystarczyzbada¢jedenztychprzypadków,powiedzmy r>r 0 .Wtedymamy

0 <r − r 0 <b .Odejmuj¡crówno±ci a = qb + r , a = q 0 b + r 0 odsiebie

stronamiotrzymujemy0=( q − q 0 ) b +( r − r 0 ),ast¡d r − r 0 =( q 0 − q ) b b

cojestsprzeczno±ci¡zzało»eniem r<b .Awi¦cprzepadek r>r 0 jest

niemo»liwy.Podobniejestwprzypadku r<r 0 .Tooznacza,»erozkładjest

jednoznaczny.

Liczb¦ r nazywamy reszt¡zdzielenia a przez b .

Przykłady

1. a =4509 ,b =145,wtedy a =31 · 145+14,awi¦creszt¡zdzielenia4509

przez145jest r =14.

2.Liczba a mo»eby¢ujemnanaprzykładdla a = − 4509 ,b =145mamy

− 4509=( − 32) · 145+131,awi¦creszt¡zdzielenia − 4509przez145jest

r =131.

Trzebapami¦ta¢,»eresztazawszemusiby¢liczb¡wi¦ksz¡odzera.

Niech a,b b¦d¡liczbamicałkowitymiiniech b 6 =0.Wtedymówimy,»e

liczba b dzieli a (lub,»e b jestdzielnikiem a )je±liistniejeliczbacałkowita c ,

»e a = bc .Fakt,»eliczba b dzieli a zapisujemysymbolicznie b | a ,ajesliliczba

b niedzieli a topiszemy b - a .

Naprzykład24 | 96bo96=4 · 24.Podobnie − 4 | 24bo24=( − 6) · ( − 4).

Liczba3niedzieliliczby7,awi¦cmo»emyzapisa¢3-7.

Mo»nałatwozauwa»y¢,»eje±liliczba b dzieli a toliczba b dzieli − a .

Mamywi¦cprostestwierdzenie:

Liczbyai − amaj¡takiesamedzielniki.

Inn¡prost¡uwag¡jest,»e1dzielika»d¡niezerow¡liczb¦całkowit¡,oraz

»eka»daniezerowliczbacałkowitadzieli0.

Nast¦pnedwieuwagidotycz¡ilo±cidzielnikówdanejliczbycałkowitej:

(i)dzielnikiniezerowejliczbycałkowitej a s¡mniejszelubrówne | a | ,

(ii)niezerowaliczbacałkowitamasko«czon¡ilo±¢dzielników.

Naprzykładdzielnikamiliczby12s¡ ± 1 , ± 2 , ± 3 , ± 4 , ± 6 , ± 12.

Niech a i b b¦d¡liczbamicałkowitymi,zktórychprzynajmniejjednajest

ró»naodzera.Wtedy najwi¦kszymwspólnymdzielnikiem tychliczb

nazywamynajwi¦ksz¡liczb¦całkowit¡ d ,któradzielijednocze±nie a i b .Naj-

wi¦kszywspólnydzielnikoznaczamyprzezNWD( a,b )ijestonwyznaczony

(wtymprzypadku)jednoznacznie.Inaczejmówi¡c d =NWD( a,b )wtedyi

tylkowtedygdy

(i) d | a i d | b ,

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

Zpowy»szejdeﬁnicjiwida¢,»eNWD( a,b ) 1.

NaprzykładNWD(12 , 30)=6.

Problemem,którytusi¦pojawiajestkonstruktywnewyznaczanienaj-

wi¦kszegowspólnegodzielnikadwóchliczb.Problemtenmo»narozwi¡za¢

nast¦puj¡co.Zauwa»my,»eNWD( a,b )=NWD( − a,b )=NWD( a, − b )=

NWD( − a, − b ).Zatemmo»emyograniczy¢si¦doprzepadkugdy a i b s¡

liczbamidodatnimi.Załó»mydodatkowo,»e a b .Oczywi±cieje±li b | a to

NWD( a,b )= b iproblemuniema.Przypu±¢my,»e b - a wtedymo»emy a

podzieli¢przez b zniezerow¡reszt¡:

a = q 0 b + r 0 , 0 <r 0 <b

Je±liliczba c dzieli a idzieli b totaliczbamusidzieli¢równie» r 0 .Oznaczato,

»ezbiórdzielnikówliczb a,b jesttakisamjakzbiórdzielnikówliczb b,r 0 ,a

wi¦crównie»NWD( a,b )=NWD( b,r 0 ).Mo»nawi¦cprocesdzieleniazreszt¡

kontynuowa¢wnast¦puj¡cysposób:

a = q 0 b + r 0 , 0 <r 0 <b

b = q 1 r 0 + r 1 , 0 <r 1 <r 0

r 0 = q 2 r 1 + r 2 , 0 <r 2 <r 1

r 1 = q 3 r 2 + r 3 , 0 <r 3 <r 2

. . .

awi¦cwnast¦pnymkrokudzielimypoprzedni¡reszt¦przeznast¦pn¡reszt¦.

Mo»nazauwa»y¢,»e

NWD( a,b )=NWD( b,r 0 )=NWD( r 0 ,r 1 )=NWD( r 1 ,r 2 )= ...

iponiewa»ci¡gresztjest±ci±lemalej¡cymci¡giemliczbcałkowitychnie-

ujemnychtoposko«czonejilo±cikrokówmusimyotrzyma¢reszt¦równ¡zero.

Zgodniezwcze±niejszymstwierdzeniemnajwi¦kszymwspólnymdzielnikiem

liczb a i b b¦dzieostatnianiezerowaresztawtymprocesie.Opisanyalgorytm

znajdowanianajwi¦kszegowspólnegodzielnikanosinazw¦ AlgorytmuEu-

klidesa .Poka»emyteraznaprzykładziedziałanietegoalgorytmu.

Zadanie Wyznaczy¢przypomocyAlgorytmuEuklidesanajwi¦kszywspólny

dzielnikliczb324i148.Awi¦cwykonujemykolejnedzielenia:

324=2 · 148+28

148=5 · 28+8

28=3 · 8+4

8=4 · 2+0

Ostatni¡niezerow¡reszt¡jest4.Tooznacza,»eNWD(324 , 148)=4.Jest

todu»olepszyiszybszyalgorytmodrozkładanialiczbnaczynnikipierwsze.

Poka»emy,»epowy»szyalgorytmmo»eposłu»y¢doznalezieniatakichliczb

całkowitych u,v ,»e324 u +148 v =4.Najpierwzprzedostatniegokroku

mo»emywyznaczy¢4jako:

4=28 − 3 · 8

dalejkrokwy»ejmamy8=148 − 5 · 28podstawiaj¡ctodowcze±niejotrzy-

manegowzorumamy:

4=28 − 3 · 8=28 − 3 · (148 − 5 · 28)=16 · 28 − 3 · 148

wkrokuwy»ejmamyformuł¦na28,wi¦cmo»emyotrzyma¢:

4=28 − 3 · 8=16 · 28 − 3 · 148=16 · (324 − 2 · 149) − 3 · 148=16 · 324 − 35 · 148

codajenamjednozmo»liwychrozwi¡za«całkowitychrównania324 u +

148 v =4,amianowicie u =16 ,v = − 35.

Awi¦cAlgorytmEuklidesamo»nawykorzystywa¢nietylkodoposzuki-

wanianajwi¦kszegowspólnegodzielnikadwóchliczb,alerównie»dorozwi¡-

zywaniarówna«typu

ax + by =NWD( a,b )

.Awi¦cprawdziwejestnast¦puj¡ceTwierdzenie.

Twierdzenie2 Niecha,bb¦d¡dwiemaliczbamicałkowitymizktórychprzy-

najmniejjednaliczbajestró»naod 0 .Wtedyistniej¡liczbycałkowiteu,v,

takie»e

ua + vb = NWD ( a,b )

Zpowy»szegotwierdzeniawynikanatychmiastnast¦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 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 .

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: