Matematyka Dyskretna 1, Polibuda, Matematyka

[ Pobierz całość w formacie PDF ]
Teoria liczb II
1.
Algorytm Euklidesa
Algorytm Euklidesa jest algorytmem obliczaj
,
acym
NWD
(
a,b
) dla
a,b
2
N. Jest zdecydowanie
szybszy ni» popularnie stosowany algorytm rozkładania liczb na czynniki pierwsze i patrzenia,
które s
,
awspólne.
Załó»my bez straty ogólno±ci, »e
a > b
. Algorytm opiera si
,
ena spostrze»eniu, »e
NWD
(
a,b
) =
NWD
(
b,a
mod
b
). Zauwa»my, »e
a
mod
b
=
a
−
b
[
b
]. A zatem je±li
d
|
a
i
d
|
b
, to
d
|
a
−
b
[
b
],
czyli
d
|
a
mod
b
. Podobnie je±li
d
|
a
−
b
[
b
] i
d
|
b
, to
d
|
a
. A zatem zbiór wspólnych dzielników
a
i
b
jest taki sam, co zbiór wspólnych dzielników
b
i
a
mod
b
, a wi
,
ec i najwi
,
eksze elementy w
tych zbiorach s
,
arówne.
Skoro wiemy, »e
NWD
(
a,b
) =
NWD
(
b,a
mod
b
), to mo»emy kontynuowa¢ t
,
eoperacj
,
ea» do
otrzymania 0. Wtedy ostatnia otrzymana niezerowa liczba to wła±nie
NWD
(
a,b
).
Przykład: NWD(87,72)=NWD(72,15)=NWD(15,12)=NWD(12,3)=NWD(3,0)=3
2.
Dla ka»dych a,b
2
N
istniej
,
atakie x,y
2
Z
, »e ax
+
by
=
NWD
(
a,b
)
.
Dowód: mo»na pokaza¢ przez indukcj
,
e, »e ka»da otrzymana w algorytmie Euklidesa liczba
jest postaci
ak
+
bl
, gdzie
k,l
2
N. Na pewno
a
=
a
·
1 +
b
·
0,
b
podobnie, wi
,
ec pocz
,
atek
indukcji jest. Je±li w pewnym momencie mamy
c
=
ak
1
+
bl
1
i
d
=
ak
2
+
bl
2
, to wtedy
c
mod
d
=
c
−
d
[
d
] =
ak
1
+
bl
1
−
(
ak
2
+
bl
2
)
·
e
, gdzie
e
2
Z, wi
,
ec
c
mod
d
te» postaci
ak
+
bl
.
Zatem na ko«cu dojdziemy do
NWD
(
a,b
), które te» b
,
edzie tej postaci.
Zauwa»my, »e w tej sytuacji mamy, »e gdy
a
?
b
to istniej
,
a
x,y
2
Z takie, »e
ax
+
by
= 1.
3.
NWD
(
a,b
)
·
NWW
(
a,b
) =
a
·
b
Dowód: rozpatrzmy pewn
,
aliczb
,
epierwsz
,
a
p
i wykładnik, w którym wyst
,
epuje z lewej i z prawej
strony. Je±li
p
-
a
i
p
-
b
, to sprawa jest prosta, wykładniki to odpowiednio 0 i 0, czyli s
,
arówne.
Je±li
p
-
a
, a
p
|
b
, to powiedzmy, »e maksymalny wykładnik
p
w
b
to
. Wtedy w
NWD
(
a,b
)
wykładnik jest 0, a w
NWW
(
a,b
) -
. A zatem równie» si
,
esumuje. Gdy obie liczby s
,
apodzielne
przez
p
w pot
,
egach odpowiednio
i
, to wykładnik przy
NWD
(
a,b
) b
,
edzie min(
,
), a przy
NWW
(
a,b
) b
,
edzie max(
,
), a wi
,
ec tak»e po obu stronach wykładniki sumuj
,
asi
,
edo tej samej
liczby. Skoro
p
była dowoln
,
aliczb
,
apierwsz
,
a, to znaczy, »e liczby po obu stronach s
,
afaktycznie
równe.
4.
Ci
,
ag Fibonacciego
Ci
,
ag Fibonacciego definiuje si
,
enast
,
epuj
,
aco:
F
0
= 0
,F
1
= 1
,F
n
+2
=
F
n
+1
+
F
n
. Warto zna¢ jego
pierwsze kilka warto±ci - 0
,
1
,
1
,
2
,
3
,
5
,
8
,
13
,
21
,
34
,
55
,...
- pomaga to dostrzec ci
,
ag Fibonacciego
w zadaniach, które w tre±ci wcale go nie maj
,
a, a zauwa»enie, »e tak naprawd
,
emowa o tym
ci
,
agu praktycznie rozwi
,
azuje zadanie. Ci
,
ag ten posiada sporo ciekawych własno±ci, niektóre z
nich to:
1. NWD
(
F
n
+1
,F
n
) = 1
Mo»emy zastosowa¢ algorytm Euklidesa i dostajemy:
NWD
(
F
n
+1
,F
n
) =
NWD
(
F
n
,F
n
−
1
) =
...
=
NWD
(
F
2
,F
1
) =
NWD
(
F
1
,F
0
) =
NWD
(1
,
0) = 1
1
2. F
n
=
F
n
−
1
F
n
+1
+ (
−
1)
n
+1
Dowodzimy poprzez indukcj
,
e.
Pocz
,
atek:
F
1
=
F
2
·
F
0
+ 1, zgadza si
,
e.
Krok:
F
n
+1
=
F
n
+1
(
F
n
+
F
n
−
1
) =
F
n
F
n
+1
+
F
n
+1
F
n
−
1
=
F
n
F
n
+1
+
F
n
+ (
−
1)
n
+1+1
=
F
n
(
F
n
+1
+
F
n
) + (
−
1)
n
+2
=
F
n
F
n
+2
+ (
−
1)
n
+2
3.n
|
m
)
F
n
|
F
m
Rozpatrujemy reszty modulo
F
n
.
F
0
0
,F
1
1
,F
2
1
,F
3
2
...F
n
0, wi
,
ec je±li
F
n
+1
k
, to
F
n
+2
k,F
n
+3
2
k...F
2
n
F
n
·
k
0. Podobnie
F
3
n
0 itd.
Warto zauwa»y¢, »e maj
,
ac dane 2 kolejne wyrazy ci
,
agu mo»emy si
,
ecofa¢, czyli znajdowa¢
poprzednie wyrazy, tzn. 2 kolejne wyrazy tego ci
,
agu okre±laj
,
acały ci
,
ag.
Konsekwencj
,
atego jest, »e reszty modulo
k
dla ka»dego
k
2
N powtarzaj
,
asi
,
e, czyli je»eli
wyst
,
apił ju» kiedy± wyraz np. podzielny przez
k
, to b
,
edzie ich niesko«czenie wiele.
Istnieje wzór jawny na ci
,
ag Fibonacciego, tak zwany wzór Bineta:
F
n
=
p
5
(
1 +
p
5
)
n
−
p
5
(
1
−
p
5
2
)
n
Warto wiedzie¢, »e taki istnieje, ale nie koniecznie trzeba go zna¢.
5.
Liczb pierwszych jest niesko«czenie wiele
Dowód: Dowód przeprowadzimy nie wprost. Przypu±¢my, »e jest sko«czenie wiele liczb pierw-
szych, niech b
,
ed
,
ato:
p
1
,p
2
,...,p
n
. Rozwa»my liczb
,
e
p
=
p
1
p
2
p
3
...p
n
+ 1. Zauwa»my, »e
p
1
-
p,p
2
-
p...p
n
-
p
, a zatem
p
dzieli si
,
etylko przez 1 i przez sam
,
asiebie, wi
,
ec jest liczb
,
a
pierwsz
,
a. Dodatkowo
p
jest wi
,
eksza od wszystkich
p
i
, wi
,
ec wcze±niej rozpatrywane liczby nie
były wszystkimi liczbami pierwszymi, w ten sposób doszli±my do sprzeczno±ci.
6.
Małe twierdzenie Fermata
Niech
p
b
,
edzie liczb
,
apierwsz
,
a,
n
2
N
,p
-
n
. Wtedy zachodzi
n
p
n
mod
p
(inna wersja:
n
p
−
1
1 mod
p
).
Dowód: Rozpatrzmy zbiór
A
=
{
n,
2
n,
3
n,...,
(
p
−
1)
n
}
mod
p
. Poka»emy, »e
A
=
{
1
,
2
,...,p
−
1
}
. Najpierw zauwa»my, »e wszystkie liczby postaci
in
mod
p
s
,
az zakresu od 1 do
p
−
1, bo
n
?
p
oraz
i
?
p
. Oprócz tego wszystkie te liczby s
,
aró»ne. Przypu±¢my, »e
in
mod
p
=
jn
mod
p
. Wtedy
p
|
in
−
jn
, czyli
p
|
n
(
i
−
j
). Jednak
p
?
n
, wi
,
ec
p
|
i
−
j
. Skoro 1
¬
i,j
¬
p
−
1,
to
i
−
j
= 0, czyli
i
=
j
. A zatem ka»de dwie liczby tej postaci s
,
aró»ne. Mamy wi
,
ec
{
n,
2
n,...,
(
p
−
1)
n
}
mod
p
=
{
1
,
2
,...,p
−
1
}
mod
p
. Po wymno»eniu stronami dostajemy:
n
p
−
1
(
p
−
1)!
(
p
−
1)! mod
p
, jednak (
p
−
1)!
?
p
, wi
,
ec
n
p
−
1
1 mod
p
, c.n.d.
2
2
7.
Tw. Eulera
Niech
n
2
N
,a
?
n
, wtedy
a
'
(
n
)
1 mod
n
.
Najpierw wyja±nijmy, »e
'
(
n
) jest liczb
,
aliczb wzgl
,
ednie pierwszych z
n
mniejszych od
n
,
'
(
n
) =
|{
1
¬
k
¬
n
:
k
?
n
}|
. Zauwa»my, »e je±li
p
jest liczb
,
apierwsz
,
a, to
'
(
p
) =
p
−
1, bo
wszystkie liczby mniejsze od
p
s
,
az ni
,
awzgl
,
ednie pierwsze, a
'
(
p
k
) =
p
k
−
1
(
p
−
1), bo nie s
,
az
ni
,
awzgl
,
ednie pierwsze tylko liczby podzielne przez
p
, czyli co
p
-ta. Jednocze±nie je»eli
a
?
b
,
to
'
(
ab
) =
'
(
a
)
'
(
b
), w ten sposób mo»na ju» obliczy¢
'
(
n
) dla ka»dego
n
2
N.
Zwró¢my uwag
,
e, »e małe twierdzenie Fermata jest szczególnym przypadkiem twierdzenia Eu-
lera, gdy»
'
(
p
) =
p
−
1. Przejd¹my teraz do dowodu tw. Eulera, b
,
edzie on bardzo podobny do
dowodu małego tw. Fermata.
Dowód: niech
A
=
{
ka
: 1
¬
k
¬
n,k
?
n
}
mod
n
. Poka»emy, »e
A
=
{
k
: 1
¬
k
¬
n,k
?
n
}
mod
n
=
B
. Ka»da liczba
ka
mod
n
s
,
az zakresu od 1 do
n
−
1 i na dodatek
s
,
awzgl
,
ednie pierwsze z
n
, bo
k
?
n
i
a
?
n
. Poza tym je±li
ka
mod
n
=
la
mod
n
, to
k
2
A
ka
Q
k
2
A
k
mod
n
, z czego wynika, »e
a
'
(
n
)
Q
k
2
A
k
Q
k
2
A
k
mod
n
. Jednak poniewa»
Q
k
2
A
k
?
n
, to
a
'
(
n
)
1 mod
n
, c.n.d.
8.
Chi«skie tw. o resztach
Niech
n
1
,n
2
,...,n
k
2
N
,n
i
?
n
j
dla
i
6
=
j,a
1
,a
2
,...,a
k
2
N. Wtedy istnieje dokładnie
jedna liczba
a
2{
0
,
1
,...,n
1
n
2
...n
k
−
1
}
taka, »e
a
a
i
mod
n
i
.
Dowód: zauwa»my, najpierw, »e mo»liwych układów reszt modulo
n
1
,n
2
,...,n
k
jest
n
1
n
2
...n
k
.
Zauwa»my te» »e dla ka»dej liczby z przedziału od 0 do
n
1
n
2
...n
k
−
1 układ reszt, które daje ona
modulo
n
i
jest ró»ny. Gdyby
x
i
y
dawały ten sam układ reszt, to
n
1
|
x
−
y,n
2
|
x
−
y,...,n
k
|
x
−
y
, czyli
n
1
n
2
...n
k
|
x
−
y
, a to dla
x
i
y
z naszego przedziału mo»liwe jest tylko przy
x
=
y
.
A zatem wszystkie układy reszt s
,
aprzyjmowane i to ka»dy dokladnie raz, czyli jakkolwiek so-
bie nie wybierzemy »
,
adanego układu znajdziemy dokładnie jedn
,
aliczb
,
ew naszym przedziale
realizuj
,
ac
,
ate reszty, c.n.d.
9.
Tw. Wilsona
n
2
N
,n >
1 jest liczb
,
apierwsz
,
awtedy i tylko wtedy gdy (
n
−
1)!
−
1 mod
n
Dowód:
„
(
” Najpierw dowodzimy w lewo.
Dowodzimy nie wprost. Załó»my, »e
n
jest zło»one. A zatem
n
=
p
1
·
p
2
,n > p
1
,p
2
>
1. Wtedy
p
1
|
(
n
−
1)!, wi
,
ec (
n
−
1)! nie jest wzgl
,
ednie pierwszy z
n
. Sprzeczno±¢.
„
)
” Teraz dowodzimy w prawo.
Liczba
p
jest pierwsza, wi
,
ec dla ka»dego
k
istnieje odwrotno±¢ modulo
p
, czyli
V
k
W
l
:
k
·
l
1
mod
n
. Tylko dwie liczby s
,
aw parze ze sob
,
a, s
,
ato 1 oraz
p
−
1, gdy» aby
p
|
x
2
−
1 potrzeba,
by
p
|
(
x
+ 1)(
x
−
1), czyli
p
|
(
x
−
1) lub
p
|
(
x
+ 1). Liczb od 1 do
p
−
1 jest parzy±cie wiele,
wi
,
ec wszystkie dobior
,
asi
,
ew pary, czyli (
p
−
1)!
1 mod
p.
3
n
|
a
(
k
−
l
), czyli
n
|
k
−
l
, czyli
k
=
l
. Zatem
Q
[ Pobierz całość w formacie PDF ]

  • zanotowane.pl
  • doc.pisz.pl
  • pdf.pisz.pl
  • mement.xlx.pl

    • Tematy