Algebra 2-01 arytmetyka liczb ...

[ Pobierz całość w formacie 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
1
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-
2
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»szejdefinicjiwida¢,»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
3
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
4
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¡definicj¦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
.
5
[ Pobierz całość w formacie PDF ]