Algebra 0-04 pierścienie.pdf

Wykład4

Okre±limyterazpewn¡wa»n¡klas¦pier±cieni.

Twierdzenie1 Niechm,n 2 Z .Je±lin> 0 toistniejedokładniejednapara

liczq,r,»e:

m = qn + r, 0 ¬ r<n.

Liczb¦ r nazywamyreszt¡zdzielenia m przez n icz¦stooznaczamyj¡przez

m n .Zauwa»my,»eresztazawszejestliczb¡wi¦ksz¡lubrówn¡zeroijest

mniejszaodliczbyprzez,któr¡dzielimy.

Przykłady

1. m =26 ,n =6,wtedymamy26=4 · 6+2,wi¦cresztazdzielenia26przez

6wynosi2.

2. m = − 26 ,n =6,wtedymamy26=( − 5) · 6+4,wi¦cresztazdzielenia

-26przez6wynosi4.

3. m =5 ,n =7,wtedymamy5=0 · 7+5,wi¦cresztazdzielenia5przez7

wynosi5.

Niech Z n = { 0 , 1 ,...,n − 1 } ,gdzie n 2 N ,n> 0,wtedywzbiorze Z n

mo»emyokre±li¢działania+ n , · n wnast¦puj¡cysposób:

a + n b =( a + b ) n

a · n b =( a · b ) n

awi¦csum¦iiloczynw Z n okre±lamyjakoreszt¦zdzieleniazwykłejsumyi

zwykłegoiloczynuprzez n .Okre±lmynast¦puj¡c¡funkcj¦:

f n :Z ! Z n

f n ( x )=resztazdzielenialiczby x przez n .Wtedyfunkcja f n mawłasno±ci:

f n ( x + y )= f n ( x )+ n f n ( y )

f n ( x · y )= f n ( x ) · n f n ( y )

Niech r,s oznaczaj¡resztyzdzielenia x i y przez n wtedymamy x = an +

r,y = bn + s .St¡d x + y =( a + b ) n + r + s i f n ( x + y )= f n ( r + s )i f n ( x )= r

oraz f n ( y )= s .Poniewa»0 ¬ r,s<n tozgodniezdeﬁnicj¡funkcji f n i

dodawania+ n otrzymujemy»¡dan¡równo±¢.

Twierdzenie2 Systemalgebraiczny ( Z n , + n , · n ) jestpier±cieniemprzemien-

nymzjedynk¡.

Dowód Wszystkiewłasno±cipier±cieniamo»nasprawdzi¢korzystaj¡czfunk-

cji f n .Naprzykładje±lichcemyudowodni¢ł¡czno±¢towe¹mydowolneele-

menty a,b,c 2 Z n .Wtedymamy:

a + n ( b + n c )= f n ( a +( b + c ))= f n (( a + b )+ c )=( a + n b )+ n c

Innewłasno±cipokazujesi¦podobnie.Elementemneutralnymdodawaniajest

0,mno»eniajest1.Elementemprzeciwnymdo a 2 Z n jest n − a .

Działania+ n , · n nazywasi¦zwykledodawaniemimno»eniemmodulo n ,

apier±cie«( Z n , + n , · n )pier±cieniemresztmodulo n .Mo»nate»zdeﬁniowa¢

pot¦gowanienp. a 2 w Z n rozumiemyjako a · n a itd...Wsensiepier±cienia Z n

mo»emyformalnieu»ywa¢dowolnychliczbcałkowitychimo»emypowiedzie¢,

»eliczba a = b w Z n je±li f n ( a )= f n ( b ).Cotodaje?Mo»nawprostysposób

wykonywa¢pewnedziałanianp.je±lichcemyobliczy¢7 · 9 (4+ 9 5)towystarczy

obliczy¢ilewynosi7 · (4+5)w Z ,apotemwzi¡¢reszt¦zdzieleniawyniku

przez9.Mo»nate»inaczejpost¦powa¢naprzykładje±lichcemyobliczy¢2 100

wpier±cieniu Z 5 tołatwiejjestwykonywa¢odrazupewneobliczeniamodulo

5,bo2 4 =1w Z 5 ,awi¦c2 100 =(2 4 ) 25 =1 25 =1.

Zadanie Skonstruowa¢tabelkidziała«wpier±cieniu Z 5 .

· n 01234

000000

101234

202413

303142

404321

Zadanie Obliczy¢888 2 wpier±cieniu Z 889 .

Rozwi¡zanie Poniewa»wpier±cieniu Z 889 liczba888= − 1to888 2 =

( − 1) 2 =1.

Zadanie Rozwi¡za¢równanie15 · 19 x =1w Z 19 .

Rozwi¡zanie Trzebawyznaczy¢liczb¦,którawymno»onaprzez15modulo

19danam1.T¦liczb¦mo»nawyznaczy¢badaj¡cwszystkieresztymodulo

19.Poprzetestowaniuwszystkichliczbmodulo15,stwierdzimy,»ejedynym

rozwi¡zaniemnaszegorównaniajest14.

Opiszemyterazogóln¡metod¦odwracanialiczbmodulo n

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 ,aje±liliczba

b niedzieli a topiszemy b - a .

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

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

+ n 01234

001234

112340

223401

334012

440123

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.

Opiszemyterazalgorytm,którypozwalawprostysposóbwyznacza¢naj-

wi¦kszywspólnydzielnikdwóchliczb.Załó»my,»e a b .Oczywi±cieje±li b | a

toNWD( 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.Jestto

du»olepszyiszybszyalgorytmodrozkładanialiczbnaczynnikipierwsze.

Poka»emyteraz,»ekorzystaj¡czpowyzszegoalgorytmumo»naposzu-

kiwa¢całkowitychrozwi¡za«równania ax + by =NWD( a,b ).Jakmo»na

znale¹¢teliczby?

Wprzypadkuliczb a =324, b =148równanietorozwi¡zujemywna-

st¦puj¡cysposób.Najpierwzprzedostatniegokrokumo»emywyznaczy¢4

jako:

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 )

Wprostzpowy»szychrozumowa«mo»nawywnioskowa¢nast¦puj¡ceTwier-

dzenie:

Twierdzenie3 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.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: