4 Die ganzen Zahlen

Descartes nannte die negativen ganzen Zahlen auch ``falsche Zahlen''.

4.1 Konstruktion von $\mathbb{Z}$.
Um auch für natürliche Zahlen $a<b$ Gleichungen der Form $a=b+x$ zu lösen, benötigen wir ein Inverses (welches wir mit $-n$ bezeichnen) zu jedem $n\in\mathbb{N}\setminus\{0\}$. Da in jeder Gruppe das neutrale Element invers zu sich selbst ist, ist $-0=0$. Somit sollte die Menge der ganzen Zahlen durch $\mathbb{Z}=\mathbb{N}\cup\{-n:n\geq 1,n\in\mathbb{N}\}$ gegeben sein.

Um die Operationen für $\mathbb{Z}$ ohne Fallunterscheidungen zu definieren, betrachten wir für $a,b\in\mathbb{N}$ ein Symbol $x_{a,b}$ (die virtuelle Lösung der Gleichung $a=b+x$). Die Menge $\mathbb{Z}$ sollte auch als Menge $\{x_{a,b}:a,b\in\mathbb{N}\}$ aller Lösungen beschrieben werden können. Wir versuchen nun mit diesen Lösungen $x$ zu rechnen. Natürlich erwarten wir, daß $x_{a,b}$ durch $a-b:=a+(-b)$ gegeben ist, wobei $-b$ das (zu findende) Inverse von $b$ ist. Wegen $(b+b')+(x_{a,b}+x_{a',b'})= (b+x_{a,b})+(b'+x_{a',b'})=a+a'$ sollte $x_{a,b}+x_{a',b'}=x_{a+a',b+b'}$ sein. Dies sieht man auch wie folgt ein:

$$x_{a,b}+x_{a',b'} =a-b+a'-b'=(a+a')+((-b)+(-b)')$$

$$=(a+a')-(b+b')=x_{a+a',b+b'}.$$

Also betrachten wir die Halbgruppe $\mathbb{N}^2=\mathbb{N}\times \mathbb{N}$ mit der komponentenweisen Addition. Die Abbildung $(a,b)\mapsto x_{a,b}$ sollte surjektiv $\mathbb{N}^2\to \mathbb{Z}$ sein. Nach Übungsaufgabe (19) existiert eine bijektive Abbildung von $\mathbb{N}^2/{\sim}\to\mathbb{Z}$, $[(a,b)]_{\sim}\mapsto x_{a,b}$ von der Menge der Äquivalenzklassen bzgl. der Relation $(a,b)\sim (a',b')$ $:\Leftrightarrow$ $x_{a,b}=x_{a',b'}$. Wir können also virtuelle Lösungen $x_{a,b}$ mit Äquivalenzklassen $[(a,b)]_\sim$ von Paaren natürlicher Zahlen identifizieren. Es sollte $(a,b)\sim (c+a,c+b)$ sein, denn aus $b+x_{a,b}=a$ folgt $(c+b)+x_{a,b}=c+(b+x_{a,b})=c+a$. Also definieren wir $(a,b)\sim (a',b')$ $:\Leftrightarrow$ $a+b'=b+a'$. Dies entspricht auch der Idee $x_{a,b}=a-b$, denn dann ist $x_{a,b}=x_{a',b'}$ genau dann, wenn $a-b=a'-b'$, also nach Addition von $b+b'$, wenn $a+b'=a'+b$ ist.

Diese Relation ist mit der Addition verträglich (man sagt $\sim$ ist eine Kongruenzrelation), denn aus $(a,b)\sim (a',b')$ und $(c,d)\sim (c',d')$ folgt $(a+c,b+d)\sim (a'+c',b'+d')$ da

$$(a+c)+(b'+d')=(a+b')+(c+d')=(a'+b)+(c'+d)=(a'+c')+(b+d).$$

Folglich können wir Äquivalenzklassen $[(a,b)]_{\sim}$ addieren, indem wir ihre Repräsentanten (=Elemente) addieren.

$$[(a,b)]_{\sim} + [(c,d)]_{\sim} := [(a+c,b+d)]_{\sim}.$$

Somit erhalten wir eine kommutative Halbgruppe $\mathbb{N}^2/{\sim}$ mit neutralem Element $0:=[(0,0)]_{\sim}$. Für jedes $x=[(a,b)]_{\sim}\in \mathbb{Z}$ existiert ein Inverses $-x:=[(b,a)]_{\sim}$, denn $x+(-x)=[(a,b)]_{\sim}+[(b,a)]_{\sim}=[(a+b,b+a)]_{\sim}=[(0,0)]_{\sim}$. Also ist $\mathbb{N}^2/{\sim}$ sogar eine Gruppe, die wir mit gutem Recht als $\mathbb{Z}$ bezeichnen könnten. Allerdings ist $\mathbb{N}$ keine Teilmenge von $\mathbb{Z}$ sondern nur injektiv in $\mathbb{Z}$ vermöge $n\mapsto [(n,0)]_{\sim}$ eingebettet. Um $\mathbb{N}$ wirklich als Teilmenge zu erhalten, könnte man noch die Klassen $[(n,0)]_{\sim}$ durch $n$ in $\mathbb{Z}$ ersetzen.

Die Multiplikation auf $\mathbb{N}$ erweitert sich ebenfalls zu einer Operation auf $\mathbb{N}^2$ durch $(a,b)\cdot (a',b'):=(a\cdot a'+b\cdot b',a\cdot b'+a'\cdot b)$. Idee dabei ist $(a-b)\cdot (a'-b')=(aa'+bb')-(ab'+a'b)$. Auch diese Operation ist mit $\sim$ verträglich, denn aus $(a,b)\sim (a',b')$, also $a+b'=a'+b$, folgt $ac+bd+a'd+b'c=(a+b')c+(a'+b)d=(a'+b)c+(a+b')d=ad+bc+a'c+b'd$, d.h. $(a,b)\cdot (c,d)\sim (a',b')\cdot (c,d)$. Also ist auch $(\mathbb{Z},\cdot)$ eine kommutative Halbgruppe mit $1=[(1,0)]_{\sim}$. Weiters gilt das distributiv-Gesetz, d.h. $(\mathbb{Z},+,\cdot)$ ist ein kommutativer Ring mit $1$.

Allerdings ist $(\mathbb{Z},+,\cdot)$ kein Körper den außer $\pm 1$ hat kein einziges Element $x\in\mathbb{Z}$ ein multiplikatives Inverses. Trotzdem ist $\mathbb{Z}$ ein Integritätsbereich, d.h. es ist ein kommutativer Ring mit 1, der nullteilerfrei ist.

4.2 Unendliche Zifferndarstellung negativer ganzer Zahlen.
Wendet man das übliche Verfahren zur Berechnung der Differenz $x-y$ zweier Zahlen auch im Falle $x<y$ an so erhält man z.B. für Dezimalzahlen $123-321=-198$ in der Binärdarstellung:

$$\begin{array}{cccccccccccccccccc} & & & & & & ... ...0&0&0&0&0&1&\\ \hline \dots&1&1&1&1&1&1&0&0&1&1&1&0&1&0&\\ \end{array}$$

insbesonders ergibt $0-321$

$$\begin{array}{cccccccccccccccccc} & & & & & & ... ...0&0&0&0&0&1&\\ \hline \dots&1&1&1&1&1&0&1&0&1&1&1&1&1&1&\\ \end{array}$$

Diese Folgen sind nach links durch unendlich viele 1'er zu ergänzen. Die unendliche Binärzahlentwicklung einer negativen ganzen Zahl $-x$ erhalten wir also dadurch, daß wir in der Binärzahlentwicklung von $x-1$ an allen Stellen (auch bei den führenden Nullen) 1 und 0 austauschen, oder bei gleicher Wirkung alle Stellen von $x$ komplementieren und danach 1 dazuzählen. Der Vorteil dieser Darstellung ist, daß man bei der Addition, Subtraktion und Multiplikation keine Fallunterscheidungen mehr machen muß und Subtraktionen $x-y$ wirklich als Addition $x+(-y)$ berechnet werden können. Der Nachteil, daß man dafür unendlich viele Schritte ausführen muß, verschwindet am Computer, denn da haben Zahlen ohnehin üblicherweise nur eine fixe Maximallänge (wie z.B. bei Byte's von 8 Binärstellen, bei short von 16, bei int(eger) von 32 und bei long von 64 Binärstellen). Man muß sich allerdings dazumerken, ob man die Zahlen als positiv oder möglicherweise als negative Zahlen auffassen will (also unsigned oder signed Datentypen spezifizieren). Im ``signed'' Fall verwendet der Computer das höchste Bit einer Zahl als Vorzeichen, z.B. bei Bytes:

binär	hexadezimal	unsigned byte	signed byte
00000000	00	0	0
00000001	01	1	1
&vellip#vdots;	&vellip#vdots;	&vellip#vdots;	&vellip#vdots;
01111110	7E	126	126
01111111	7F	127	127
10000000	80	-128	128
10000000	81	-127	129
&vellip#vdots;	&vellip#vdots;	&vellip#vdots;	&vellip#vdots;
11111110	FE	-2	254
11111111	FF	-1	255

4.3 Restklassenringe.
Auch die Restklassenringe $\mathbb{Z}_m$ für $0\ne m\in\mathbb{N}$ sind kommutative Ringe mit 1, wobei die Addition und Multiplikation von Klassen durch

$$[x]_m+[y]_m := [x+y]_m$$

$$[x]_m\cdot[y]_m := [x\cdot y]_m$$

gegeben sind. Es ist $\mathbb{Z}_m$ genau dann ein Integritätsbereich, wenn $m$ eine Primzahl ist: Denn aus $m=a\cdot b$ mit $1<a,b<m$ folgt, daß $[a]_m\cdot [b]_m=[a\cdot b]_m=[m]_m=0$ ist, obwohl $[a]_m\ne 0\ne [b]_m$. Ist hingegen $m$ eine Primzahl, so ist $0=[a]_m\cdot [b]_m=[a\cdot b]_m$ genau dann, wenn $m$ das Produkt $a\cdot b$ teilt, und somit eine Faktor teilt. Dessen Restklasse ist dann aber 0.

Insbesonders sind $\mathbb{Z}_2$ und $\mathbb{Z}_3$ Integritätsbereiche (und sogar Körper, wie wir in (4.7) zeigen werden) $\mathbb{Z}_4$, $\mathbb{Z}_{16}$ und $\mathbb{Z}_{256}$ hingegen nicht einmal Integritätsbereiche.

4.4 Definition.
Es sei $R$ ein Integritätsbereich und $a,b\in R$. Dann heißt $b$ Teiler von $a$ falls ein $q\in R$ existiert mit $a=b\,q$. Ein größter gemeinsamer Teiler (kurz ggT) von $a$ und $b$ ist ein Element $d\in R$ welches $a$ und $b$ teilt, und welches von jedem anderen gemeinsamen Teiler geteilt wird. Falls 1 ein größter gemeinsamer Teiler ist, so heißen $a$ und $b$ relativ prim.

4.5 Proposition. Charakterisierung des ggT.
Die Menge $\operatorname{ggT}(a,b)$ der größte gemeinsame Teiler zweier Elemente $a$ und $b$ eines Integritätsbereichs erhält man durch Multiplikation eines ggT mit allen Einheiten (d.h. invertierbaren Elementen).

In $\mathbb{Z}$ ist also der ggT nur bis auf ein Vorzeichen $\{\pm1\}$ eindeutig bestimmt.

Beweis. Es sei $d$ ein Teiler von $a$ und $u$ eine Einheit. Dann ist auch $u\,d$ ein Teiler von $a$: Nach Voraussetzung existiert ein $q\in R$ mit $a=b\,q$. Dann ist $a=b\,u^{-1}\,u\,q$, also wird $a$ durch $u\,q$ geteilt.

Sei nun $d$ ein ggT von $a$ und $b$ und $u$ eine Einheit, dann ist $u\,d$ ebenfalls ein ggT von $a$ und $b$: Nach obigen ist $u\,d$ ein Teiler von $a$ und $b$. Sei $t$ ein weiterer gemeinsamer Teiler von $a$ und $b$. Dann ist $t$ ein Teiler von $d$. Da $u$ invertierbar ist, existiert $u^{-1}$ und ist auch eine Einheit. Somit ist auch $u^{-1}\,t$ ein Teiler von $d$, d.h. es existiert ein $q\in R$ mit $d=u^{-1}\,t\,q$, also $u\,d=t\,q$, somit ist $t$ auch Teiler von $u\,d$.

Sei schließlich $d'$ ein weiterer ggT von $a$ und $b$. Dann teilen sich $d$ und $d'$ gegenseitig, also existieren $u'\in R$ und $u\in R$ mit $d=d'\,u'$ und $d'=d\,u$, also ist $d'\,(1-u'\,u)=0$ und da wir Nullteilerfreiheit vorausgesetzt haben (und Teiler nicht 0 sind) ist $1=u'\,u$, also $u$ eine Einheit mit $d'=u\,d$. 'ed

Euklid'ischer Algorithmus.
Man kann den ggT von $a,b\in\mathbb{Z}$ wie folgt bestimmen (ohne die aufwendige Bestimmung der Primfaktorenzerlegung von $a$ und $b$). Sei dazu O.B.d.A. $a\geq b\geq 0$. Wir setzen $r_0:=a$ und $r_1:=b$ und berechnen mittels Division mit Rest rekursiv $q_k$ und $r_k$ mit $r_{k-1}=q_{k+1}r_{k}+r_{k+1}$ mit $0\leq r_{k+1}<r_k$. Nach höchstens $\vert b\vert$ Schritten ist $r_{k+1}=0$. Das letzte $r_k\ne 0$ ist dann ein ggT $d$ von $a$ und $b$.

$$r_0 = q_2\,r_1 +r_2$$

$$r_1 = q_3\,r_2 +r_3$$

$$\;\;\vdots$$

$$r_{k-3} =q_{k-1}\,r_{k-2}+r_{k-1}$$

$$r_{k-2} =q_{k} \,r_{k-1}+r_{k}$$

$$r_{k-1} =q_{k+1}\,r_{k} +0$$

Weiters existieren $a',b'\in\mathbb{Z}$ mit $d=a'\,a+b'\,b$.

Beweis. Aus der letzten Gleichung der Rekursion folgt, daß $r_{k-1}$ durch $d:=r_k$ geteilt wird, aus der vorletzen, daß $r_{k-2}$ ebenfalls durch $d$ geteilt wird, und induktiv, daß $b=r_1$ und schließlich auch $a=r_0$ durch $d$ geteilt wird.

Weiters können wir die Gleichungen rekursiv bei der vorletzten Gleichung beginnend nach oben fortschreitend auflösen und erhalten:

$$d=r_k = r_{k-2}-q_k\, r_{k-1}$$

$$= r_{k-2}-q_k\,(r_{k-3}-q_{k-1}\, r_{k-2}) = r_{k-3}\,(-q_k) + r_{k-2}\,(1-q_k\,q_{k-1})$$

$$\vdots$$

$$= a''\, r_1 + b''\,r_2$$

$$= a''\, r_1 + b''\,(r_0-q_2\,r_1) = b''\, r_0 + (a''-b''\,q_2)\,r_1$$

$$= a'\,a + b'\, b$$

mit gewissen $a',b'\in\mathbb{Z}$.

Falls ein $t\in\mathbb{Z}$ sowohl $a$ als auch $b$ und damit die rechte Seite teilt, so teilt $t$ auch die linke Seite $d$. Also ist $d$ ein ggT von $a$ und $b$.     []

4.6 Beispiel.
Wir bestimmen mittels Euklid'ischen Algorithmus den ggT von $209$ und $77$: Fortgesetze Division mit Rest liefert:

$$209 = 77 \cdot 2 + 55,$$

$$77 = 55 \cdot 1 + 22,$$

$$55 = 22\cdot 2 + 11,$$

$$22 = 11\cdot 2 + 0,$$

also ist $ggT(209,77)=\{\pm 11\}$ und

$$11 = 55 - 22\cdot 2 = 55 - (77-55\cdot 1)\cdot 2 = 55\cdot 3 -77\cdot 2$$

$$=(209-77\cdot 2)\cdot 3-77\cdot 2 = 209\cdot 3 -77\cdot 8.$$

4.7 Folgerung.
Eine Restklasse $[a]\in \mathbb{Z}_m$ ist genau dann eine Einheit, wenn 1 ein ggT von $a$ und $m$ ist, d.h. $a$ und $m$ relativ prim sind.
Somit ist $\mathbb{Z}_m$ genau dann ein Körper, wenn $m$ eine Primzahl ist.

Beweis. Wegen dem Euklid'ischen Algorithmus ist $1$ genau dann ein ggT von $a$ und $m$, wenn $\exists a',m'\in \mathbb{Z}$: $1=a'\,a+m'\,m$, d.h. $[1]_m=[a']_m\cdot [a]_m$, also $[a]_m$ ein (links)-Inverses besitzt.     []

Polynome

3.32 Definition.
Unter einem reellen Polynom $p$ verstehen wir eine Funktion $p:\mathbb{R}\to\mathbb{R}$, welche durch $p(x):=\sum_{k=0}^n p_k\,x^k$ mit $n\in\mathbb{N}$ und gewissen Koeffizienten $p_k\in\mathbb{R}$ gegeben ist.

Manchmal ist es günstiger Polynome als formal unendliche Summen $\sum_k p_k\, x^k$ zu schreiben, wobei halt in Wirklichkeit fast alle Koeffizienten $p_k$ gleich 0 sind, d.h. alle bis auf endlich viele.

Wir können Funktionen $f,g:\mathbb{R}\to\mathbb{R}$ addieren und multiplizieren:

$$f+g :x\mapsto f(x)+g(x),$$

$$f\cdot g:x\mapsto f(x)\cdot g(x).$$

In diesem Sinn sind Summe und Produkt von Polynomen wieder Polynome, denn

$$\Bigl(\sum_k a_k\, x^k\Bigr)+\Bigl(\sum_k b_k\,x^k\Bigr) =\sum_k (a_k+b_k)\,x^k$$

$$\Bigl(\sum_i a_i\, x^i\Bigr)\cdot \Bigl(\sum_j b_j\,x^j\Bigr) = \sum_{i,j} a_i\,b_j\,x^{i+j} = \sum_n\Bigl(\sum_{i+j=n} a_i\,b_j\Bigr) x^n$$

$$= \sum_n\Bigl(\sum_{i=0}^n a_i\,b_{n-i}\Bigr) x^n$$

Idee beim vorletzten Gleichungszeichen ist, anstelle in der Tabelle

$$\begin{array}{r\vert l\vert l\vert l\vert l\ve... ...3b_2x^5 & a_3b_3x^6 & \hdots \\ \hline \vdots & & & & & \\ \end{array}$$

nacheinander über alle Zeilen zu summieren, besser über die Diagonalen mit gleicher Summe $i+j=n$ zu summieren.

Da reelle Polynome $p$ eindeutig durch ihre Koeffizienten $p_k$ beschrieben werden (siehe (4.13a)), können wir diese auch als die Teilmenge

$$\{(p_0,p_1,p_2,\dots)\in \mathbb{R}^\mathbb{N}:p_k=0$$ für fast alle $$k\in\mathbb{N}\}$$

von $\mathbb{R}^\mathbb{N}$ auffassen.

Allgemeiner sei nun $R$ ein kommutativer Ring mit 1 und $X$ eine Menge. Dann ist auch die Menge $R^X$ aller Abbildungen $X\to R$ ein kommutativer Ring mit 1 vermöge der Operationen:

$$f+g :x\mapsto f(x)+g(x)$$

$$f\cdot g :x\mapsto f(x)\cdot g(x)$$

Die Menge $\{x\mapsto p_0+p_1\,x+\dots+p_n\,x^n:n\in\mathbb{N},p_0,\dots,p_n\in R\}$ der polynomialen Funktionen bildet einen Teilring mit $1$ von $R^X$. Achtung, dieser ist nicht für alle $R$ nullteilerfrei: Für $R=\mathbb{Z}_2$ ist z.B. $0=x-x^2=x\cdot (1-x)$. Wir betrachten also besser nur die Koeffizienten und definieren Polynome in $R$ als endliche Folgen $(p_0,p_1,\dots,p_n)$ von Koeffizienten $p_0,\dots,p_n\in R$, die wir uns auch durch 0'en aus $R$ zu einer unendlichen Folge $(p_0,\dots,p_n,0,\dots)$ fortgesetzt denken dürfen. Man definiert Addition und Multiplikation von solchen Polynomen analog zu obigen durch

$$(a_0, a_1,\dots,a_n,0,\dots)+(b_0,b_1,\dots,b_m,0,\dots) := (a_0+b_0,a_1+b_1,\dots,0,\dots)$$

$$(a_0, a_1,\dots,a_n,0,\dots)\cdot(b_0,b_1,\dots,b_m,0,\dots)$$

$$:= (a_0b_0,a_0b_1+a_1b_0,a_0b_2+a_1b_1+a_2b_0,\dots,a_nb_m,0,\dots)$$

Es ist leicht zu zeigen, daß dadurch die Menge der Polynome zu einen kommutativen Ring mit 1 wird (man schreibt üblicherweise $R[x]$ für diesen), und wir werden in (4.9) zeigen, daß dies ein Integritätsbereich ist falls $R$ einer ist.

Jedes Polynom $(a_0,a_1,\dots,a_n)$ können wir natürlich als polynomiale Funktion $R\to R$ vermöge $r\mapsto a_0+a_1\,r+\dots+a_n\,r^n$ auffassen. Dies liefert einen Homomorphismus (d.h. Abbildung, die mit Addition und Multiplikation verträglich ist) $R[x]\to R^R$, der aber für endliche Ringe $R$ nicht injektiv zu sein braucht. Für $R=\mathbb{Z}_2$ z.B. ist die zum Monom $x\mapsto x^k$ gehörende polynomiale Funktion $\mathbb{Z}_2\to\mathbb{Z}_2$ für jedes $k\geq 1$ durch die Identität $\operatorname{id}_{\mathbb{Z}_2}$ gegeben.

Man schreibt statt der Folge $(p_0,p_1,\dots)$ üblicherweise die ``formale Summe'' $\sum_k p_k\, x^k$ damit die Formeln für die Addition und Multiplikation sich durch formale Anwendung des distributiv-Gesetzes ergeben.

Der Grad $\operatorname{grad}(p)$ eines Polynoms $p\ne 0$ ist der größte Index $k$ der nicht verschwindenden Koeffizienten $p_k$ diese Polynoms, oder wie man auch sagt der Index des führenden Koeffizienten.

Es ist $\operatorname{grad}(a+b)\leq\max\{\operatorname{grad}(a),\operatorname{grad}(b)\}$ und $\operatorname{grad}(a\cdot b)=\operatorname{grad}(a)+\operatorname{grad}(b)$ falls $R$ ein Integritätsbereich ist. Für das Nullpolynom ergäbe sich daraus $\operatorname{grad}(0)=\operatorname{grad}(0\cdot b)=\operatorname{grad}(0)+\operatorname{grad}(b)$ für alle Polynome $b\ne 0$. Diese Gleichung in $\operatorname{grad}(0)$ ist in $\mathbb{Z}$ nicht lösbar, aber $-{\infty}$ erfüllt sie, also setzt man $\operatorname{grad}(0):=-{\infty}$.

Die Summanden $p_k\, x^k$ heißen auch Monome vom Grad $k$.

Man schreibt oft $R_n[x]$ für die Menge der Polynome vom Grad kleiner oder gleich $n$.

4.8 Lemma.
Ein reelles Polynom $p$ (oder allgemeiner Polynom mit Koeffizienten in einen Körper) besitzt genau dann ein multiplikatives Inverses, d.h. ist eine Einheit, wenn $\operatorname{grad}(p)=0$, d.h. $p$ konstant aber nicht 0 ist.

Beweis. Sei $p$ eine Einheit, also existiert ein Polynom $q$ mit $1=q\cdot p$ und somit ist $0=\operatorname{grad}(1)=\operatorname{grad}(q)+\operatorname{grad}(p)$, also ist $\operatorname{grad}(p)=0$, d.h. $p$ ist konstant.     []

4.9 Folgerung.
Falls $R$ ein Integritätsbereich ist, so ist auch der Ring $R[x]$ der Polynome mit Koeffizienten in $R$ ein solcher.

Beweis. Es seien $p\ne 0$ und $q\ne 0$ Polynome. Dann ist $\operatorname{grad}(p)\geq 0$ und $\operatorname{grad}(q)\geq 0$ und somit $\operatorname{grad}(p\cdot q)=\operatorname{grad}(p)+\operatorname{grad}(q)\geq 0$, also $p\cdot q\ne 0$.     []

4.10 Bemerkung.
Wie bei ganzen Zahlen, können wir auch bei reellen Polynomen (oder allgemeiner bei Polynomen mit Koeffizienten in einem Körper) die Division mit Rest durchführen: Wir fassen dazu die Koeffizienten $a_k$ als $k$-te ``Ziffer'' von rechts gezählt auf. Z.B. ist

$$(6x^4+4x^3+5x^2+x+3)=(2x^2+1)\cdot(3x^2+2x+1)+(-x+2),$$

denn

$$\begin{array}{rrrrrrl} (& +6x^4 & +4x^3 & +5x^... ...&\pm1x^1& \\ \hline & & & 0 & -x^1 & +2x^0 & \text{Rest}\\ \end{array}$$

Dies entspricht der Division mit Rest $64513=201\cdot321 + (-1)2$. Beachte also, daß bei Polynomen beliebige (auch negative oder rationale oder komplexe) ``Ziffern'' auftreten können.

4.11 Horner-Schema.
Es sei $p$ ein Polynom $p(x):=\sum_{k=0}^n a_k\, x^k$ mit Koeffizienten aus einem Ring $R$ und $\xi \in R$. Division durch $x-\xi$ mit Rest liefert ein Polynom $q(x):=\sum_{k=0}^{n-1} b_k\,x^k$ und Rest $r\in R$ mit $p(x)=q(x)\,(x-\xi )+r$. Wir versuchen nun eine Formel für Koeffizienten $b_k$ und Rest $r$ zu finden. Es ist

$$\sum_j a_j\,x^j = p(x) = (x-\xi )\,q(x)+r = (x-\xi )\,\sum_j b_j\,x^j+r$$

$$= \sum_j b_j\,x^{j+1} -\sum_j b_j\,\xi \,x^j + r.$$

Koeffizientenvergleich liefert $a_n=b_{n-1}$, sowie $a_j=b_{j-1}-b_j\,\xi$ für $n>j>0$ und $a_0=-b_0\,\xi +r$. Daraus ergibt sich die gewünschte Rekursionsformel $b_{k-1}=a_k+\xi \, b_k$ mit $b_{n}:=0$ und $b_{-1}:=r$. Dies nennt man Horner-Schema.

$$\begin{array}{r\vert\vert c\vert c\vert c\vert... ... & \dots & b_0=b_1 \xi +a_1 & b_{-1}=b_0 \xi +a_0 \\ \hline \end{array}$$

Setzt man in obige Gleichung $\xi$ anstelle von $x$ so erhält man $p(\xi )=0\cdot q(\xi )+r=r$, also ist der Rest $r=b_{-1}$ der Funktionswert von $p$ an der Stelle $\xi$.

Induktive Anwendlung liefert das vollständige Horner-Schema zur Darstellung eines Polynoms $p$ als Linearkombination von Potenzen von $(x-\xi )$, d.h. $p(x)=\sum_{k=0}^n c_k\, (x-\xi )^k$.

4.12 Definition.
Unter einer Nullstelle einer Funktion $f:X\to\mathbb{R}$, versteht man ein $\xi \in X$ mit $f(\xi )=0$. Falls $f$ ein Polynom ist, so spricht man auch von einer Wurzel $\xi$ von $f$.

4.13 Proposition.
Es sei $p\in R[x]$ ein Polynom und $\xi \in R$. Dann gilt:
$p(\xi )=0$ $\Leftrightarrow$ $x-\xi$ teilt $p$:

Beweis. Da $p(\xi )$ gerade der Rest von $p$ bei Division durch $x-\xi$ ist, ist dies offensichtlich.     []

4.13a Folgerung. Koeffizientenvergleich.
Es sei $0\ne p\in R[x]$ ein Polynom vom Grad $n$ und $R$ ein Integritätsbereich. Dann besitzt $p$ höchstens $n$ Nullstellen. Ist also $\sum_{k=0}^n p_k\,x^k=0$ für unendlich viedle (oder zumindestens $n+1$ viele $x\in R$), dann sind alle Koeffizienten $p_k=0$.

Beweis. Es seien $\xi _1,\dots,\xi _n$ paarweise verschiedene Nullstellen von $p$. Nach (4.13) wird $p$ von $x-\xi _1$ geteilt, also existiert ein Polynom $p'$ mit $p(x)=(x-\xi _1)\,p'(x)$. Folglich sind $\xi _2,\dots,\xi _n$ auch Nullstellen on $p'$ und mittels Induktion folgt $p(x)=\prod_{i=1}^n (x-\xi _i)\,q(x)$ für ein Polynom $q\ne 0$. Damit ist $\operatorname{grad}(p)=\sum_{i=1}^n 1+\operatorname{grad}(q)\geq n$.     []

5.19 Proposition.
Es sei $p$ ein Polynom mit Koeffizienten in $\mathbb{Z}$ und $\frac{r}{s}$ eine rationale Nullstelle von $p$ mit relativ primen $r$ und $s$. Dann wird der führende Koeffizient von $p$ durch $s$ und der 0-te Koeffizient durch $r$ geteilt.

Dies kann dazu verwendet werden die rationalen Nullstellen eines Polynoms durch Probieren zu finden.

Beweis. Es sei also $0=\sum_{k=0}^n p_k\,(r/s)^k$ mit $p_n\ne 0$ oder äquivalent $0=\sum_{k=0}^n p_k\,r^k\,s^{n-k}$. Alle bis auf den Term für $k=0$ sind durch $r$ teilbar, also auch dieser, d.h. $r$ teilt den niedersten Koeffizienten $p_0$. Weiters sind alle bis auf den Term für $k=n$ durch $s$ teilbar, also auch dieser, d.h. $s$ teilt den führenden Koeffizenten $p_n$.     []

4.14 Proposition. Vieta'scher Wurzelsatz.
Der $k$-te Koeffizient von $\prod_{j=1}^n (x-\xi _j)$ ist durch $(-1)^{n-k}\,\sigma _{n-k}(\xi _1,\dots,\xi _n)$ gegeben, wobei $\sigma _j$ die $j$-te elementarsymmetrische Funktion ist.

Im Fall $n=2$ bedeutet dies $(x-\xi _1)\cdot (x-\xi _2)=x^2-x(\xi _1+\xi _2)+\xi _1\,\xi _2$.

Beweis. Wenn man $\prod_j(x-\xi _j)$ ausmultipliziert erhält man eine Summe von $n$-fachen Produkten, die dadurch entstehen, daß aus jeder der $n$ Klammern jeweils $x$ oder $-\xi _j$ gewählt wird. Der Koeffizient von $x^k$ wird also gerade durch solche Auswahlen erhalten, wo genau $k$-mal $x$ und immer sonst die entsprechenden $-\xi _j$ gewählt werden. Diese Auswahlen werden also genau durch die $n-k$-elementigen Teilmengen $J$ von $\{\xi _1,\dots,\xi _n\}$ beschrieben und tragen $(-1)^{n-k}\,\prod_{j\in J}\xi _j$ zum Koeffizienten bei.     []

4.15 Euklid'ischer Algorithmus für Polynome.
Wie für ganze Zahlen können wir den Euklid'ische Algorithmus auch dazu verwenden um einen ggT in $\mathbb{R}[x]$ zweier Polynome $p_0$ und $p_1$ zu bestimmen. Wir müssen dazu nur rekursive Division mit Rest ausführen bis wir bei Rest 0 landen. Der letzte Rest davor ist dann ein ggT.

Sei z.B. $p:x\mapsto x^4-1$ und $q:x\mapsto x^3+x$. Fortgesetze Division mit Rest liefert

$$(x^4-1) = (x^3+x)\cdot x+(-x^2-1),$$

$$(x^3+x) = (-x^2-1)\cdot (-x) + 0,$$

also ist $-x^2-1$ ein ggT von $p$ und $q$ und

$$-x^2-1 = (x^4-1)\cdot 1+(x^3+x)\cdot (-x).$$

Komposition von Polynomen.
Wenn wir Polynome als Abbildungen $\mathbb{K}\to\mathbb{K}$ auffassen, so können wir diese auch zusammensetzen, und erhalten somit allgemein eine Komposition:

$$\Bigl(\sum_{k=0}^n a_k\, x^k\Bigr) \o\Bigl(\su... ...n a_k \Bigl(\sum_{j=0}^m b_j\, x^j\Bigr)^k = \sum_{k=0}^{nm} c_k\, x^k,$$

wobei

$$c_0 = \sum_{k=0}^n a_k \, b_0^k$$

$$c_1 = \sum_{k=1}^n a_k \, k\, b_0^{k-1}\, b_1$$

$$\vdots$$

Es gilt $\operatorname{grad}(p\o q)=\operatorname{grad}(p)\cdot\operatorname{grad}(q)$.

4.16 Bemerkung.
Jenes Polynom minimalen Grades, welches an den Stellen $x_0,\dots,x_n$ die Werte $y_0,\dots,y_n$ hat, heißt Interpolationspolynom und ist durch die Lagrange'sche Interpolationsformel

$$p(x)=\sum_{j=0}^n y_j \frac{\prod_{i\ne j}(x-x_i)}{\prod_{i\ne j}(x_j-x_i)}$$

gegeben.

Beweis. Offensichtlich ist

$$p(x_k) =\sum_{j=0}^n y_j \,p_j(x_k) = y_k,$$

$$p_j(x) := \frac{\prod_{i\ne j}(x-x_i)}{\prod_{i\ne j}(x_j-x_i)},$$

$$p_j(x_k) = \left\{\begin{array}{ll} 1&\text{für }k=j\\ 0&\text{sonst.}\end{array}\right.$$

    []

4.17 Inklusions-Exklusions-Prinzip.

$$\Bigl\vert\bigcup_{i=1}^n A_i\Bigr\vert = \! \sum_{\emptyset\ne J\subseteq \{1,\dots,n\}} (-1)^{1+\vert J\vert}\; \Bigl\vert\bigcap_{j\in J} A_j\Bigr\vert$$

$$\Bigl\vert\bigcap_{i=1}^n A_i^c\Bigr\vert = \!\sum_{J\subseteq \{1,\dots,n\}} (-1)^{\vert J\vert}\; \Bigl\vert\bigcap_{j\in J} A_j\Bigr\vert,$$

$$\bigcap_{j\in\emptyset} A_j:=X$$

Mit $\vert A\vert$ bezeichnen wir die Anzahl der Elemente der Menge $A$.

Beweis. Wir zeigen die erste Formel mittels Induktion nach $n$:
( $n=1$) ist offensichtlich, denn dann existiert nur ein $\emptyset\ne J\subseteq \{1,\dots,n\}$, nämlich $J=\{1\}$.
( $n=2$) Es sind $A\cup B=(A\setminus B)\cup (A\cap B)\cup (B\setminus A)$ sowie $A=(A\setminus B)\cup (A\cap B)$ und $B=(B\setminus A)\cup (A\cap B)$ disjunkte Zerlegungen und somit

$$\vert A\cup B\vert =\vert A\setminus B\vert+\vert A\cap B\vert+\vert B\setminus A\ve... ...rt A\vert-\vert A\cap B\vert+\vert A\cap B\vert+\vert B\vert-\vert A\cap B\vert$$

$$=\vert A\vert+\vert B\vert-\vert A\cap B\vert$$

( $n+1$) Es sei $C:=\bigcup_{i=1}^n A_i$ und $B_i:=A_i\cap A_{n+1}$. Unter Verwendung der Induktionsannahme für die $A_i$ und die $B_i$ mit $1\leq i\leq n$ erhalten wir aus dem Fall $n=2$:

$$\Bigl\vert\bigcup_{i=1}^{n+1}A_i\Bigr\vert = \vert C\cup A_{n+1}\vert = \vert C\vert+\vert A_{n+1}\vert-\vert C\cap A_{n+1}\vert$$

$$= \sum_{\emptyset\ne J\subseteq \{1,\dots,n\}}(-1)^{1+\vert J\ver... ... J}A_j\Bigr\vert + \vert A_{n+1}\vert + \Bigl\vert\bigcup_{i=1}^n B_i\Bigr\vert$$

$$= \sum_{\emptyset\ne J\subseteq \{1,\dots,n\}}(-1)^{1+\vert J\ver... ...eq \{1,\dots,n\}}(-1)^{1+\vert J\vert} \Bigl\vert\bigcap_{j\in J} B_j\Bigr\vert$$

$$= \!\sum_{\emptyset\ne J\subseteq \{1,\dots,n\}}\!(-1)^{1+\vert J... ...\}}\!(-1)^{1+\vert J\vert} \Bigl\vert\bigcap_{j\in J} A_j\cap A_{n+1}\Bigr\vert$$

$$= \sum_{\emptyset\ne J\subseteq \{1,\dots,n+1\}}(-1)^{1+\vert J\vert} \Bigl\vert\bigcap_{j\in J}A_j\Bigr\vert$$

Die zweite Formel folgt mittels de Morgan'schen Gesetzen aus der ersten, denn

$$\bigcap_{i=1}^n A_i^c=X\setminus \bigcup_{i=1}^n A_i.{\rm\quad[]}$$