Cryptography Reference
In-Depth Information
3.1.3 Division mit Rest
Bei der Konstruktion von
Z
n
aus
Z
spielt
Division mit Rest
die zentrale Rolle.
[
]
Division mit Rest
kann man auch in
K
X
durchführen, wenn
K
ein Körper ist.
Satz 3.2
(Division mit Rest)
Es sei K ein Körper. Zu je zwei Polynomen f
,
g
∈
K
[
X
]
, wobei g
=
0
, existieren eindeu-
∈
[
]
tig bestimmte Polynome q
,
r
K
X
mit
=
+
<
f
gq
r und
deg
r
deg
g
.
=
{
−
∈
[
]
}
Beweis.
Die Menge
M
:
f
gh
;
h
K
X
ist nicht leer. Daher existiert ein
Polynom
r
∈
M
mit minimalem Grad. Es gilt somit
r
=
f
−
gq
für ein
q
∈
K
[
X
]
.
=
≥
=
Wäre
n
:
deg
r
m
:
deg
g
, so bilde
g
r
n
g
−
m
X
n
−
m
r
=
−
∈
:
r
M
.
Dieses Polynom
r
liegt in
M
, da es die Form
f
−
gh
hat. Wir berechnen nun:
r
n
X
n
r
r
n
X
n
r
n
−
1
X
n
−
1
r
n
g
−
m
g
m
−
1
X
n
−
1
=
+
+
···
+
r
0
−
+
+
···
r
n
−
1
r
n
g
−
m
g
m
−
1
X
n
−
1
X
n
−
2
=
−
+(
···
)
+
···
.
Es ist also deg
r
<
deg
r
im Widerspruch zur Wahl von
r
. Das zeigt die Existenz
von
q
und
r
mit den geforderten Eigenschaften.
Gäbe es ein weiteres Paar
q
,
r
∈
q
, mit
K
[
X
]
,
q
=
gq
+
r
mit deg
r
, deg
r
<
=
+
=
f
gq
r
deg
g
,
so folgte für
r
−
q
)
=
(
−
r
g
q
aus Lemma 3.1 der Widerspruch
r
−
q
)
deg
(
r
)
<
deg
g
≤
deg
g
+
deg
(
q
−
.
q
und damit auch
r
r
.
Daher gilt
q
=
=
Wir ziehen eine Folgerung:
Korollar 3.3
Ist a Nullstelle eines Polynoms f
∈
K
[
X
]
,d.h. f
(
a
)=
0
, so gibt es ein q
∈
K
[
X
]
mit
=(
−
)
f
X
a
q
.
Beweis.
Nach dem Satz zur Division mit Rest existieren zu den Polynomen
f
und
X
−
∈
[
]
<
=
(
−
)
∈
a
Polynome
q
,
r
K
X
mit deg
r
1
deg
X
a
, also
r
K
, und
f
=(
X
−
a
)
q
+
r
.
=
(
)=(
−
)
(
)+
=
Wir setzen
a
ein und erhalten 0
f
a
a
a
q
a
r
, somit gilt
r
0.
