Algebra 2-02 arytmetyka liczb ...

[ Pobierz całość w formacie 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¡definicj¦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.
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
2
gdziep
i
,q
j
s¡pierwszetos
=
rije±lip
1
¬
p
2
¬
...
¬
p
r
,q
1
¬
q
2
¬
...
¬
q
s
to
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
)
n
lim
n
!1
ln
n
=1
3
mniejszyb¡d¹równyod
p
n.
  [ Pobierz całość w formacie PDF ]