\def\bari{\bar{i}}% \def\barj{\bar{j}}% \section*{Inleiding} In dit Hoofdstuk hebben we systematisch enkele resultaten verzameld over ringen, vooral polynoomringen, die we elders willen gebruiken. \section{Ringen} We herhalen eerst de definitie van ring. \begin{dfs}\rm\label{def:ring} Een {\it commutatieve ring met 1}, is een verzameling $V$ met daarop twee bewerkingen $+$ en $\times$, die voldoen aan: \newcounter{ring} \begin{list}{\rm [L\arabic{ring}]}{\usecounter{ring} \setlength{\topsep 0.6ex plus0.2ex} \setlength{\parsep 0.0ex plus0.1ex} \setlength{\itemsep 0.1ex plus0.2ex} \setlength{\labelwidth 5.0ex} \setlength{\labelsep 1.6ex} \setlength{\leftmargin 6.0ex} } \item $+$ op $V$ is associatief: $(x+ y)+ z=x+(y+ z)$, voor alle $x,y,z\in V$; \item er is een (nul)element $0\in V$ zodanig dat $0+ x=x+ 0=x$ voor alle $x\in V$; \item bij elke $x\in V$ is er een {\it tegengestelde} $-x\in V$ zodanig dat $x+(-x)=(-x) + x=0$; \item $+$ op $V$ is commutatief: $x+y=y+x$ voor alle $x,y\in V$; \item $\times$ op $V$ is associatief: $(x\times y)\times z=x\times(y\times z)$, voor alle $x,y,z\in V$; \item er is een (eenheids)element $1\in V$ zodanig dat $1\times x=x\times 1=x$ voor alle $x\in V$; \addtocounter{ring}{1} \item $\times$ op $V$ is commutatief: $x\times y=y\times x$ voor alle $x,y\in V$; \item de operatie $\times$ is {\it distributief} over $+$, dat wil zeggen: $x\times (y+z)=(x\times y)+(x\times z)$ en $(x+y)\times z = (x\times z)+(y\times z)$, voor alle $x,y,z\in V$. \end{list} Als [L8] niet geldt hebben we een {\it ring met 1}, voor ons kortweg {\it ring}. \end{dfs} \begin{opn}\rm Een commutatieve ring met $1$ voldoet dus aan alle eisen van een lichaam behalve de inverteerbaarheid van niet-nul elementen. Wanneer wij in het vervolg over een (commutatieve) ring spreken, bedoelen we altijd een (commutatieve) ring met $1$. Voor een deelring $U$ van $V$ eisen we ook dat het eenheidselement $1\in V$ in $U$ zit (en daar het eenheidselement is). \end{opn} \opgave{Opgave}{Laat $(R, +,\times)$ een ring zijn; bewijs dat een deelverzameling $S$ van $R$ een deelring is als: \begin{hwitemize} \item $1_R\in S$; \item als $a,b\in S$ dan ook $a-b\in S$; \item als $a,b\in S$ dan ook $a\times b\in S$. \end{hwitemize}} \opgave{Opgave}{Laat zien dat de deelverzameling van $\Z$ bestaande uit de even getallen voldoet aan L1--5 en L8--9. Dit is een commutatieve ring zonder eenheidselement, die we {\rm niet} als deelring van $\Z$ beschouwen omdat 1 er niet in zit.} \begin{vbn}\label{vb:rng}\rm De belangrijkste voorbeelden van ringen zijn, naast de licha\-men, voor ons de volgende. \newcounter{rrr} \begin{list}{\rm (\roman{rrr})}{\usecounter{rrr} \setlength{\topsep 0.6ex plus0.2ex} \setlength{\parsep 0.0ex plus0.1ex} \setlength{\itemsep 0.1ex plus0.2ex} \setlength{\labelwidth 5.0ex} \setlength{\labelsep 1.6ex} \setlength{\leftmargin 6.0ex} } \item[(i)] De gehele getallen $\Z$, met de gewone optelling en vermenigvuldiging; dit is een commutatieve ring. \item[(ii)] De ring $\Z/m\Z$, de restklassenring modulo $m$, voor een geheel getal $m>1$, met de gebruikelijke optelling en vermenigvuldiging van restklassen, zoals gedefinieerd in \ref{vbd:zmz}. Dit is steeds een commutatieve ring. \item[(iii)]\label{def:rx} Als $R$ een commutatieve ring met $1$ is (bijvoorbeeld \'e\'en van de ringen of lichamen die we hierboven zagen) kun je daaruit een nieuwe {\it ring $R[x]$ van polynomen met co\"effici\"enten in $R$} maken: de verzameling bestaat uit de polynomen of {\it veeltermen} $\sum_{i=0}^na_ix^n=a_0+a_1x+a_2x^2+\cdots+a_nx^n$, waar $n\geq 0$ een geheel getal is. De operaties zijn de {\it optelling van polynomen}: $$\sum_{i=0}^n a_ix^i + \sum_{j=0}^m b_jx^j=\sum_{i=0}^{\max(m,n)} (a_i+b_i)x^i,$$ en de {\it vermenigvuldiging van polynomen} $$(\sum_{i=0}^n a_ix^i) \times (\sum_{j=0}^m b_jx^j)=\sum_{k=0}^{m+n} (\sum_{i=0}^k a_i\times b_{k-i})x^k.$$ Hier nemen we $a_i=0$ voor alle $i>n$ en $b_j=0$ voor $j>m$. Deze polynoomring $R[x]$ is zelf weer een commutatieve ring met $1$, maar geen lichaam omdat bijvoorbeeld het polynoom $x$ geen inverse heeft. In {\bf Lineaire Algebra 1} en {\bf 2} heb je al kennis gemaakt met het speciale geval $R=\R$. \item[(iv)] In {\bf Lineaire Algebra 1} en {\bf 2} heb je ook gezien dat je vierkante matrices van re\"ele getallen kunt optellen en vermenigvuldigen. Veel algemener kunnen we bij elke commutatieve ring met $1$ een nieuwe {\it ring van $n\times n$ matrices $\Mat_n(R)$ met co\"effici\"enten in $R$} maken: de verzameling bestaat uit vierkante $n\times n$ matrices, en de operaties zijn de {\it optelling van matrices}, waar de som van $$ \pmatrix{ a_{11} & a_{12} & \cdots & a_{1n}\cr a_{21} & a_{22} & \cdots & a_{2n}\cr \vdots & \vdots & \ddots & \vdots\cr a_{n1} & a_{n2} & \cdots & a_{nn}\cr} \ \ {\rm en} \ \ \pmatrix{ b_{11} & b_{12} & \cdots & b_{1n}\cr b_{21} & b_{22} & \cdots & b_{2n}\cr \vdots & \vdots & \ddots & \vdots\cr b_{n1} & b_{n2} & \cdots & b_{nn}\cr} $$ gedefinieerd is door $$ \pmatrix{ a_{11} + b_{11} & a_{12} + b_{12} & \cdots & a_{1n} + b_{1n}\cr a_{21} + b_{21} & a_{22} + b_{22} & \cdots & a_{2n} + b_{2n}\cr \vdots & \vdots & \ddots & \vdots\cr a_{n1} + b_{n1} & a_{n2} + b_{n2} & \cdots & a_{nn} + b_{nn}\cr} $$ en {\it vermenigvuldiging van matrices}, middels het product $$ \pmatrix{ \sum_{i=1}^n a_{1i} \times b_{i1} & \sum_{i=1}^n a_{1i} \times b_{i2} & \cdots & \sum_{i=1}^n a_{1i} \times b_{in}\cr \sum_{i=1}^n a_{2i} \times b_{i1} & \sum_{i=1}^n a_{2i} \times b_{i2} & \cdots & \sum_{i=1}^n a_{2i} \times b_{in}\cr \vdots & \vdots & \ddots & \vdots\cr \sum_{i=1}^n a_{ni} \times b_{i1} & \sum_{i=1}^n a_{ni} \times b_{i2} & \cdots & \sum_{i=1}^n a_{ni} \times b_{in}\cr } $$ Met andere woorden: optellen en vermenigvuldigen van zulke matrices doe je op precies dezelfde manier als waarop je dat eerder hebt gezien in het speciale geval dat alle co\"effici\"enten re\"eel waren. Voor elke $n\geq 1$ krijgen we zo (voor gegeven commutatieve ring $R$) een ring $M_n(R)$. Als $n>1$ is die ring $\Mat_n(R)$ niet commutatief! \end{list} \end{vbn} \opgave{Opgave}{Wat is het eenheidselement, en wat is het nulelement in $R[x]$? En in $\Mat_n(R)$?} \medskip\noindent We hebben gezien dat elke ring $R$ (dus in het bijzonder elk lichaam) in ieder geval de elementen $0, 1$ bevat. Maar dan moet ook $1+1$ in $R$ zitten, een element dat we gewoonlijk met 2 aangeven. Maar let op: het kan best zijn dat $2$ gelijk is aan \'e\'en van de elementen die we al opschreven: $0$ of $1$. Maar als $1+1=1$ dan moet $1=0$ (want tel bij beide kanten de tegengestelde $-1$ op), en dat hebben we juist verboden (in Voorbeeld \ref{vb:lich}(iv)). Dus $2$ is een nieuw element \`of gelijk aan $0$. Datzelfde argument kun je herhalen: $1+1+1\in R$ komt al voor onder $\{0, 1, 2\}$ \`of het is een nieuw element; in het eerste geval moet $1+1+1=0$ (tenzij al gold $1+1=0$). \begin{dfn}\rm Laat $R$ een ring zijn; als er een natuurlijk getal $m$ bestaat zodanig dat $1+1+\cdots+1=m\times 1=0\in R$, dan is de {\it karakteristiek van $R$} het kleinste positieve natuurlijke getal met die eigenschap; als zo'n $m$ niet bestaat is de karakteristiek per definitie $0$. \end{dfn} \medskip\noindent Als de karakteristiek van $R$ gelijk aan $0$ is, dan zijn alle elementen $1, 2, 3, \ldots$ verschillend: er bestaat dan een {\it injectie} van $\Z\rightarrow R$. Omgekeerd, als er zo'n injectieve afbeelding bestaat moet de karakteristiek wel $0$ zijn. \opgave{Opgave}{Geef voor elk natuurlijk getal $m\geq 2$ twee verschillende voorbeelden van een ring van karakteristiek $m$.} \section{Eenheden en Nuldelers} Vervolgens kijken we naar twee speciale soorten elementen in een ring. \begin{dfs}\rm Een element $r$ van een ring $R$ (niet noodzakelijk commutatief) heet een {\it eenheid in $R$} als er een inverse voor $r$ in $R$ bestaat, dat wil zeggen, een element $t\in R$ met $r\times t=t\times r=1$). De inverse van $r$ geven we meestal met $r^{-1}$ aan. Een element $r\in R$ heet een {\it nuldeler in $R$} als $r\neq 0$ en er een element $s\in R$ bestaat met $s\neq 0$ zodat $r\times s=0$ of $s\times r=0$. \end{dfs} \opgave{Opgave}{Laat zien dat in een lichaam elk element dat niet 0 is een eenheid is.} \opgave{Opgave}{Geef twee elementen $r, s$ van $\Mat_2(\Z)$ met de eigenschap dat $r\times s=0$ maar $s\times r\neq 0$.} \begin{thm} Een eenheid in een ring $R$ (niet noodzakelijk commutatief) kan geen nuldeler zijn. \end{thm} \smallskip\noindent {\bf Bewijs.} Laat $r\in R$ een eenheid zijn, en veronderstel dat $r$ ook een nuldeler is. Dan is $r\neq 0$ en we veronderstellen dat er een $s\in R$ is met $s\neq 0$ en $r\times s=0\in R$. Omdat $r$ een eenheid is, is er een $t\in R$ met $t\times r=1$. Dan is $$s=1\times s=(t\times r)\times s=t\times(r\times s)=t\times 0=0,$$ dus $s=0$, in tegenspraak met bovenstaande. Het geval $s\times r=0$ gaat net zo, door rechts met $t$ te vermenigvuldigen. De aanname dat $r$ een nuldeler is leidt dus tot een tegenspraak. \opgave{Opgave}{Zij $\cdot$ een bewerking op een verzameling $V$. Definieer voor $n\geq 3$ het product $v_1\cdot v_2\cdots v_n$ inductief (voor $v_i\in V$) door $(v_1\cdot v_2\cdots v_{n-1})\cdot v_n$. Laat (met behulp van inductie naar $n$) zien dat als $\cdot$ associatief is, voor alle $n\geq 3$ en alle $k$ met $1\leq k\leq n-1$ geldt: $$(v_1\cdot v_2\cdots v_k)\cdot (v_{k+1}\cdots v_n)=v_1\cdot v_2\cdots v_n.$$} \opgave{Opgave}{Bewijs dat het eenheidselement $1\in R$ uniek bepaald is.} \opgave{Opgave}{Geef een voorbeeld van een ring zonder nuldelers waarin niet elk element (ongelijk aan 0) een eenheid is.} \opgave{Opgave}{Laat zien dat de eenheden van een ring $R$ een groep vormen onder $\times$. Deze groep geven we aan met $R^*$.} \opgave{Opgave}{Bewijs dat $\Mat_n(\R)^*$ bestaat uit de $n\times n$ re\"ele matrices met determinant ongelijk aan $0$. Deze groep geven we ook wel met $\GL_n(\R)$ aan. Waarom is dit geen ring (voor elke $n>0$)?} \opgave{Opgave}{Beschrijf $\GL_n(\Z)$, en algemener, de groep $\GL_n(R)$ voor een commutatieve ring $R$.} \opgave{Opgave}{Bewijs dat de ring $\Z/n\Z$ een lichaam is dan en slechts dan als $n$ een priemgetal is.} \opgave{Opgave}{Als $V$ een verzameling is, geven we met $P(V)$ de {\it machtsverzameling} van $V$ aan: $P(V)$ bestaat uit de deelverzamelingen van $V$. Laat zien dat $(P(V), +, \times)$ een commutatieve ring (met 1) wordt als we de optelling $+$ en vermenigvuldiging $\times$ defini\"eren door voor deelverzamelingen $A, B\subset V$ te nemen: $$ A+B=(A\cup B)\setminus (A\cap B),\qquad A\times B=A\cap B.$$ Laat ook zien dat $P(V)$ zo alleen een lichaam wordt als $\#V=1$.} \section{Gehele getallen, polynomen, en deelbaarheid} In deze paragraaf zetten we een aantal belangrijke eigenschappen van gehele getal\-len en polynomen op een rijtje, vooral eigenschappen die betrekking hebben op deelbaarheid. We willen vooral laten zien hoezeer de ringen $\Z$ en $L[x]$, voor een lichaam $L$, op elkaar lijken. \begin{dfs}\rm Laat $R$ een commutatieve ring (zoals altijd met $1$) zijn. Als $d, f\in R$ dan is $d$ een {\it deler} van $f$ (notatie $d\mid f$) als er een $q\in R$ bestaat met $f=qd$; we zeggen ook dat $d$ het element $f$ {\it deelt}, dat $f$ {\it deelbaar} is {\it door $d$ in $R$}, en dat $f$ een {\it veelvoud} is van $d$. Een {\it gemene deler} van $f, g\in R$ is een $d\in R$ die zowel $f$ als $g$ deelt; een {\it grootste gemene deler van $f$ en $g$} is een gemene deler $d\in R$ van $f$ en $g$ met de eigenschap dat elke andere gemene deler $d'$ een deler van $d$ is. Zo'n grootste gemene deler geven we aan met $\ggd(f, g)$. \end{dfs} \opgave{Opgave}{Laat zien dat elk element van een commutatieve ring een deler is van $0$.} \opgave{Opgave}{Laat zien dat elk element van een commutatieve ring deelbaar is door $1$.} \begin{dfs}\rm Een {\it polynoom over $R$} is element van $R[x]$, en dat is van de vorm $f=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0$, waar $a_i\in R$. Zo'n polynoom bestaat dus uit een som van termen $a_ix^i$; een polynoom dat uit \'e\'en zo'n term bestaat heet ook wel een {\it monoom}. De $a_i$ uit $R$ zijn de co\"effici"enten van het polynoom; gewoonlijk schrijven we alleen termen met $a_i\neq 0$ op (tenzij alle co\"effici"enten nul zijn: we schrijven dan gewoon $0$). De {\it graad van $f$} (notatie: $\deg f$) is, als $f\neq 0$ is, de hoogste macht van $x^n$ die met niet-nul co\"effici"ent voorkomt, en de co\"effici"ent van deze $x^n$ heet de {\it kopco\"effici"ent}. Als de kopco\"effici\"ent $1$ is noemen we het polynoom {\it monisch}. De co\"effici"ent $a_0$ heet de {\it constante co\"effici\"ent}. Als $a_i=0$ voor alle $i>0$ dan heet polynoom een {\it constant polynoom}. Het {\it nulpolynoom} is het constante polynoom $0$; de graad hiervan is per definitie $-\infty$. De $x$ in deze uitdrukkingen is de {\it onbepaalde}, {\it onbekende}, of {\it variabele}. De regels voor optellen en vermenigvuldigen (die $R[x]$ tot een commutatieve ring maken) zagen we al in \ref{def:rx}. Net als bij vermenigvuldiging van re\"ele getallen schrijven we vaak $f\cdot g$ of $fg$ voor het product $f\times g$ van polynomen. Merk op dat het nulelement, respectievelijk het eenheidselement van $R[x]$ de constante polynomen $0$, respectievelijk $1$ zijn. Waarschijnlijk ben je polynomen al eerder tegengekomen als {\it functies}; het is belangrijk op te merken dat we polynomen hier niet in de eerste plaats als functies beschouwen, maar als elementen van een ring. Een polynoom $f\in R[x]$ definieert wel een afbeelding $f:R\rightarrow R$ omdat we $f$ kunnen {\it evalueren}: zo is $f(r)=a_n r^n+\cdots a_1 r+a_0 1\in R$ voor $f$ als boven. We noemen $f(r)$ ook wel de {\it waarde van $f$ in $r$}. Een {\it nulpunt van $f$ in $R$} is een $r\in R$ zodanig dat $f(r)=0$. Als $R$ een deelring van $S$ is, kunnen we elementen van $R$ via de inbedding ook als elementen van $S$ opvatten; dat betekent dat we in dit geval $f\in R[x]$ ook kunnen evalueren in een $s\in S$: $f(s)\in S$. Zo zul je geen moeite hebben om $f(\pi)$ uit te rekenen als het $f$ het polynoom $x^2-1$ met gehele co\"effici\"enten is. \end{dfs} \opgave{Opgave}{Laat zien dat als $R$ geen nuldelers heeft voor de graden van polynomen geldt: $\deg fg=\deg f+\deg g$. [Let op het nulpolynoom!]} \medskip\noindent Sommige eigenschappen van $R[x]$ hangen af van die van $R$; een heel belangrijk speciaal geval is dat waar $R$ een lichaam is, dat we in deze paragraaf steeds met $L$ aangeven. \opgave{Opgave}{Bewijs dat $R[x]$ nuldelers heeft dan en slechts dan als $R$ nuldelers heeft.} \medskip\noindent We bekijken nu {\it deling met rest}, eerst voor gehele getallen. \begin{thm}\label{thm:zqr}Bij elke $n, m\in \Z$ met $m\neq 0$ bestaan er $q, r\in \Z$ zodat: $$n = q\cdot m+ r, \qquad 0\leq r<\vert m\vert ;$$ bovendien zijn deze $q$ en $r$ uniek bepaald. \end{thm} \noindent Voor polynomen geldt vrijwel eenzelfde resultaat. \begin{thm}Laat $R$ een commutatieve ring zijn; bij elke $f, g\in R[x]$, bestaan er polynomen $q, r\in R[x]$ zodat: $$f = q\cdot g+ r, \qquad \deg r<\deg g ;$$ mits de kopco\"effici\"ent $b_n$ van $g$ een eenheid in $R$ is; bovendien zijn deze $q$ en $r$ dan uniek bepaald. \end{thm} \medskip\noindent {\bf Bewijs.} Eerst bewijzen we het bestaan van $q$ en $r$, met inductie naar de graad $m=\deg f$. Omdat de kopco\"effici\"ent van $g$ inverteerbaar is, is $\deg g\geq 0$; we mogen ook aannemen dat $m=\deg f\geq \deg g=n$, want anders voldoen $q=0$ en $r=f$. Als $m=0$ dan is $f=a_0$ en $g=b_0$, en omdat bij aanname $b_n=b_0$ inverteerbaar is, geldt de gevraagde gelijkheid met $r=0$ en $q=a_0b_0^{-1}$. Laat nu $m\geq 1$; beschouw $h=f-a_mb_{n}^{-1}x^{m-n}g$. Als dit polynoom $0$ is voldoen $r=0$ en $q=a_mb_{n}^{-1}x^{m-n}$ aan de gestelde eisen. Is dit niet het geval, dan is $\deg h<\deg f$ omdat de kopco\"effici\"enten van $f$ en $a_mb_{n}^{-1}x^{m-n}g$ precies tegen elkaar wegvallen. We kunnen dan op $h$ en $g$ de inductiehypothese toepassen: er bestaan $q'$ en $r'$ met $h=q'g+r'$ en $\deg r'<\deg g$; maar dan is $$f=h+a_mb_{n}^{-1}x^{m-n}g=(a_mb_{n}^{-1}x^{m-n}+q')g+r',$$ en voldoen $q=a_mb_{n}^{-1}x^{m-n}+q'$ en $r=r'$ aan alle condities. Om de uniciteit te bewijzen veronderstellen we dat $$f=q'\cdot g+ r'=q''\cdot g+ r'',$$ beide aan de eisen voldoen. Dan is $(q'-q'')g=r''-r'$. Stel dat $r'\neq r''$. Dan is $q'\neq q''$. Omdat $b_n\in R$ een eenheid is, is $g$ geen nuldeler, en dus is (zie opgave): $$\deg(r''-r')=\deg (q'-q'')g=\deg g + \deg (q'-q'')\geq \deg g,$$ hetgeen in tegenspraak is met $\deg r''<\deg g$ en $\deg r'< \deg g$. Dus $r'=r''$, maar dan is $(q'-q'')g=0$ en moet $q'=q''$. \opgave{Opgave}{Welke aanpassingen aan bovenstaand bewijs zijn nodig om het ook te laten werken voor het geval \ref{thm:zqr} van gehele getallen?} \opgave{Opgave}{Geef twee polynomen $f, g\in\Z[x]$ waarbij je {\it geen} $q, r\in\Z[x]$ kunt vinden met $$f = q\cdot g+ r, \qquad \deg r<\deg g.$$ } \noindent Om te laten zien dat gehele getallen altijd een grootste gemene deler hebben, geven we algoritme om deze te vinden. \begin{alg}{\bf [ Euclides ]}\label{alg:eucl}\rm\hfill\break {\it Gegeven:} {\rm $m, n\in \Z$; niet beide nul}\hfill\break {\it Levert:} {\rm de positieve grootste gemene deler $d\in\Z $ van $m$ en $n$.} \begin{hwitemize} \item[{\bf [1]}] Initialiseer: $M=0$, $N=m$ and $r=n$. \item[{\bf [2]}] Herhaal de volgende stappen zolang $r\neq 0$: \begin{hwitemize} \item vervang $M$ door $N$ en $N$ door $r$; \item bepaal $q, r$ zodanig dat $M=qN+r$ met $0\leq r<\vert N\vert $; \end{hwitemize} \item[{\bf [3]}] Lever $d=\vert N\vert $ af. \end{hwitemize} \end{alg} \medskip\noindent Dit algoritme termineert omdat elke keer dat stap {\bf [2]} wordt uitgevoerd (mogelijk met uitzondering van de eerste!), de absolute waarde van $r$ strikt afneemt, en dus wordt dit uiteindelijk $0$. Het algoritme is correct omdat de grootste gemene deler van $m$ en $n$ altijd gelijk is aan de grootste gemene deler van $n$ en $r$, als $r$ de rest bij deling van $m$ door $n$ is. \opgave{Opgave}{Bewijs de laatste bewering.} \opgave{Opgave}{Waarom levert het algoritme niet altijd een niet-negatief getal af wanneer we de absoluut-strepen in stap {\bf [3]} weglaten?} \opgave{Opgave}{Als $m>n>0$ dan is $M=m$ en $N=n$ na het toepassen van stap {\bf [2]}; als $n>m>0$ dan geldt na het tweemaal toepasssen van stap {\bf [2]} dat $M=n$ en $N=m$. Laat dat zien.} \medskip\noindent In het vervolg nemen we steeds polynomen $f=a_mx^m+a_{m-1}x^{m-1}+\cdots a_1x+a_0$ en $g=b_nx^n+b_{n-1}x^{n-1}+\cdots b_1x+b_0$ uit $R[x]$, met $a_m\neq 0$ en $b_n\neq 0$. We willen bovenstaand algoritme imiteren voor het berekenen van de grootste gemene deler van twee polynomen $f$ en $g$ uit $R[x]$, met $R$ een commutatieve ring, door herhaalde deling met rest toe te passen. Dat gaat alleen maar goed als de deler $g$ een inverteerbare kopco\"effici\"ent heeft (dus bijvoorbeeld als $g$ monisch is). Voor het gemak nemen we aan dat alle niet-nul co\"effici\"enten inverteerbaar zijn door simpelweg te eisen dat $R$ een lichaam $L$ vormt. \begin{alg}{\bf [ Euclides ]}\label{alg:eucl2}\rm\hfill\break {\it Gegeven:} {\rm polynomen $f, g\in L[x]$ over een lichaam $L$} \hfill\break {\it Levert:} {\rm de monische grootste gemene deler $d\in L[x]$ van $f$ en $g$.} \begin{hwitemize} \item[{\bf [1]}] Initialiseer: $F=0$, $G=f$ and $r=g$. \item[{\bf [2]}] Herhaal de volgende stappen zolang $r\neq 0$: \begin{hwitemize} \item vervang $F$ door $G$ en $G$ door $r$; \item bepaal $q, r$ zodanig dat $F=qG+r$ met $\deg r<\deg G$; \end{hwitemize} \item[{\bf [3]}] Lever $d=G/G_k$ af waar $G_k$ de kopco\"effici\"ent van $G$ is. \end{hwitemize} \end{alg} \opgave{Opgave}{Ga na dat we in stap {\bf [2]} kunnen eisen dat $r$ monisch is. Waarom moeten we dan nog steeds in stap {\bf [3]} door de kopco\"effici\"ent delen?} \opgave{Opgave}{Als $\deg f>\deg g>0$ dan is $F=f$ en $G=g$ na het toepassen van stap {\bf [2]}; als $\deg g>\deg f>0$ dan geldt na het tweemaal toepasssen van stap {\bf [2]} dat $F=g$ en $G=f$. Laat dat zien.} \begin{vbd}\label{vb:eucl}\rm Bij wijze van voorbeeld bepalen we de monische grootste ge\-me\-ne deler van $f=x^6 + x^4 - x^3 - x$ en $g= x^5 + 2x^3 + x^2 + x + 1$ in $\Q[x]$. In stap {\bf [2]}(i) wordt $F_0=0$, $G_0=f$ en $r=g$; elke keer dat in het algoritme $F$ en $G$ vervangen worden verhogen we in dit voorbeeld de index van $F_i$ en $G_i$, en we geven de bijbehorende $q$ en $r$ dezelfde index. In stap {\bf [2]}(i) wordt dan $F_1=G_0=f$ en $G_1=r=g$. Deling met rest (bijvoorbeeld door een staartdeling) levert op dat $$F_1 = x\cdot G_1+(-x^4 - 2x^3 - x^2 - 2x),$$ dat wil zeggen: $q_1=x$ en $r_1=-x^4 - 2x^3 - x^2 - 2x$. Dus krijgen we $F_2=G_1=x^5 + 2x^3 + x^2 + x + 1$ en $G_2=-x^4 - 2x^3 - x^2 - 2x$; waarna quoti\"ent $q_2=-x+2$ rest $r_2=5x^3 + x^2 + 5x + 1$ geeft: $$F_2=(-x + 2)G_2+(5x^3 + x^2 + 5x + 1).$$ Vervolgens, met $F_3=G_2=-x^4 - 2x^3 - x^2 - 2x$ en $G_3=5x^3 + x^2 + 5x + 1$ krijgen we $q_3=1/5x-9/25$ en $r_3=9/25x^2+9/25$: $$F_3=(-{1\over5}x-{9\over 25})G_3+({9\over 25}x^2+{9\over 25}).$$ Dus $F_4=G_3=5x^3 + x^2 + 5x + 1$ en $G_4={9\over 25}x^2+{9\over 25}$, waarmee $$F_4=({125\over 9}x+{9\over 25})G_4+0.$$ Met $q_4=125/9x+9/25$ krijgen we rest $0$ en daarom termineert het algoritme na het afleveren van $G_4/{9\over 25}=x^2+1$. \end{vbd} \begin{thm}In een polynoomring $L[x]$ over een lichaam $L$ heeft elk tweetal polynomen $f,g$, niet beide $0$, een grootste gemene deler $d$; deze is bepaald op vermenigvuldiging met niet-nul elementen uit $L$ na, en daarom uniek als we opleggen dat $d$ monisch is. Het bovenstaande algoritme bepaalt deze unieke monische grootste gemene deler. \end{thm} \medskip\noindent {\bf Bewijs.} Als $f=0$ dan is $g$ een grootste gemene deler van $f$ en $g$ en omgekeerd; dus we nemen nu aan (zonder beperking der algemeenheid) dat $\deg f\geq\deg g\geq 0$. De crux van het bewijs is de opmerking dat als $d$ een gemene deler is van $f$ en $g$, dan ook van elke lineaire combinatie $af+bg$: immers, als $f=ud$ en $g=vd$ voor zekere $u,v\in R[x]$ dan is $af+bg=aud+bvd=(au+bv)d$. Passen we dit toe op $r=f-qg$, met $q, r$ bepaald uit deling met rest, dan zien we dat $d$ een gemene deler is van $f, g$ dan en slechts dan als het gemene deler van $g, r$ is: dus is de grootste gemene deler van $f, g$, gelijk aan de grootste gemene deler van $g, r$, mits \'e\'en van beide bestaat. Dit argument gaan we herhalen, als in het algoritme van Euclides. Laat daartoe $F_1=f$ en $G_1=g$ en laat $d$ een gemene deler van $f$ en $g$ zijn. Bepaal $q_1$ en $r_1$ zodat $F_1=q_1G_1+r_1$; dan zijn de gemene delers van $F_1, G_1$ dezelfde als die van $G_1, r_1$. We vervangen daarom het paar $F_1, G_1$ door $F_2=G_1, G_2=r_1$, met dezelfde gemene delers, maar met $\deg G_2=\deg r_1<\deg G_1$. Zo vinden we uit een paar $F_i, G_i$ een nieuw paar $F_{i+1}, G_{i+1}$ met dezelfde gemene delers, maar met $\deg G_{i+1}<\deg G_i$. Na eindig veel stappen vinden we $G_h$ met $\deg G_h\geq 0$ en $\deg G_{h+1}=-\infty$, dat wil zeggen, dat $G_{h+1}=0$. We zijn terug in de situatie die we allereerst bekeken en nu hebben $F_{h+1}=G_h$ en $G_{h+1}=0$ een grootste gemene deler $G_{h}$. Dat toont in alle gevallen het bestaan van een grootste gemene deler aan. Uniciteit volgt omdat voor twee verschillende grootste gemene delers $d$ en $d'$ enerzijds geldt dat $d=qd'$ en anderzijds $d'=q'd$. Tesamen is $d=qq'd$, dus $(1-qq')d=0$. Als $d\neq 0$ dan moet $1-qq'=0$ (want $L[x]$ heeft geen nuldelers), dus $qq'=1$. Dan zijn $q$ en $q'$ polynomen van graad $0$, dus constanten. Dat bewijst dat $d$ en $d'$ een constante factor schelen; eisen we dat de grootste gemene deler monisch is, dan is deze dus uniek bepaald. \medskip\noindent Een kleine toevoeging aan het algoritme van Euclides maakt het mogelijk niet alleen de moni\-sche grootste gemene deler $d=\ggd(f,g)$ van 2 polynomen te vinden, maar daarbij zogenaamde {\it multiplicatoren} $s, t\in R[x]$ met de eigenschap dat $d=s\cdot f+t\cdot g$. \medskip\noindent \begin{thm}[uitgebreide ggd]\label{st:mult}{\sl In $L[x]$ bestaat bij elk tweetal polynomen $f,g$, niet beide nul, een uniek tweetal $s, t\in L[x]$ zodanig dat $s\cdot f+t\cdot g=d$ waar $d$ de monische grootste gemene deler van $f$ en $g$ is, en zowel $\deg s<\deg g$ als $\deg t<\deg f$. } \end{thm} \begin{opm}\rm Het vinden van de multiplicatoren vereist slechts een beetje boekhouden bij het uitvoeren van het algoritme van Euclides. Het opschrijven hiervan kost onevenredig veel ruimte en laten we hier achterwege. \end{opm} \begin{vbd}\rm In het voorgaande voorbeeld vinden we: $$({5\over 9}x^2-{1\over 9}x-{7\over 9}) \cdot (x^6+x^4-x^3-x)+ (-{5\over9}x^3+{1\over 9}x^2-{2\over 9}x+1) \cdot (x^5+2x^3+x^2+x+1)=x^2+1.$$ \end{vbd} \section{Factoren en Nulpunten} Vervolgens houden we ons bezig met de vraag hoe polynomen met co\"effici\"enten uit een lichaam in factoren uiteen vallen. Wederom is de analogie met $\Z$ treffend. De volgende eenvoudige stelling drukt uit dat in een commutatieve ring delers van graad $1$ van een gegeven polynoom corresponderen met nulpunten van dat polynoom. \begin{thm}\label{st:zerofact}Als $a\in R$ en $f\in R[x]$ dan geldt: $$x-a\quad\mbox{deelt}\quad f\qquad\iff\qquad f(a)=0.$$ \end{thm} \medskip\noindent {\bf Bewijs.} Als $f$ deelbaar is door $x-a$ dan is $f=q(x-a)$, voor zekere $q\in R[x]$. Evalueren in $a$ geeft $f(a)=q(a)\cdot 0=0\in R$. Voor de omkering pas je deling met rest toe op $f$ en $g=x-a$: er is een $q\in R$ en een $r\in R[x]$ van graad kleiner dan $1$ (dus een constante $r_0\in R$) zodat $f=q(x-a)+r_0$. Maar dan is $0=f(a)=q(a)\cdot 0+r_0$, dus $r_0=0$ en $f=q(x-a)$ is deelbaar door $(x-a)$. \medskip\noindent De stelling geeft dus een eenvoudige methode om te controleren of een polynoom deelbaar is door $x-a$: reken $f(a)$ uit. Als de deling opgaat (dus $f(a)=0$) zul je nog wel een berekening (bijvoorbeeld een staartdeling) uit moeten voeren om het quotient te vinden. \opgave{Opgave}{Ga van het polynoom $f=x^6 + x^5 - 2x^4 + x^2 + x - 2\in\Z[x]$ na door welke twee polynomen $x-i$ met $i\in \{-2, -1, 0, 1, 2\}$ het deelbaar is. Voer de deling $q=f/((x-i_1)(x-i_2))$ voor die waarden ook uit.} \opgave{Opgave}{Bewijs dat $f\in R[x]$ door $x$ deelbaar is dan en slechts dan als $a_0=0$.} \opgave{Opgave}{Bewijs dat $f\in R[x]$ door $x-1$ deelbaar is dan en slechts dan als $\sum a_i=0$.} \opgave{Opgave}{Laat $f\in\R[x]$ en $z\in\C$; bewijs dat $f(z)=0$ impliceert dat $f(\bar z)=0$ (waar $\bar z$ de complex geconjugeerde van $z$ is).} \medskip\noindent De stelling die we beneden willen formuleren zal laten zien dat in $L[x]$ we elementen (net als gehele getallen) in factoren kunnen ontbinden. \begin{thm}[Hoofdstelling der Rekenkunde] Elk natuurlijk getal $n\geq 2$ is te schrijven als product van positieve machten van verschillende priemgetallen; deze schrijf\-wijze is uniek op volgorde van de factoren na. \end{thm} Eerst moeten we de elementen defini\"eren die voor polynomen de rol van priemgetallen zullen overnemen. \begin{dfs}\rm Een element $r\in R$ in een commutatieve ring $R$ zonder nuldelers heet {\it irreducibel in $R$} als geldt: $r\neq 0$ en $r$ is geen eenheid maar als $r=s\cdot t$ met $s, t\in R$ dan is $s$ een eenheid of $t$ is een eenheid in $R$. Als $r$ wel als zo'n product van niet-eenheden is te schrijven heet hij {\it reducibel}. \end{dfs} \begin{vbn}\rm In een lichaam is elk element nul of een eenheid en zijn er dus geen irreducibele elementen. In $\Z$ zijn de irreducibele elementen precies de {\it priemgetallen} en de reducibele elementen de {\it samengestelde getallen}. In een polynoomring $R[x]$ over een commutatieve ring $R$ zonder nuldelers heten de irreducibele elementen {\it irreducibele polynomen}. Als $R=L$ een lichaam is, dan zijn de irreducibele elementen de polynomen $f\in R[x]$ met $\deg f\geq 1$ waarvoor geen polynomen $g,h \in R[x]$ bestaan zodat $f=g\cdot h$ en zowel $\deg g<\deg f$ als $\deg h< \deg f$. Als $R$ geen lichaam is zijn er in het algemeen ook nog irreducibele elementen uit $R$ in $R[x]$ (irreducibele polynomen van graad 0). \end{vbn} \begin{lem}Laat $p, f, g\in L[x]$ met $L$ een lichaam. Als $p$ irreducibel is en $p$ is een deler van $f\cdot g$, dan is $p$ een deler van $f$ of $g$. \end{lem} \noindent {\bf Bewijs.} Veronderstel dat het irreducibele polynoom $p$ geen deler is van $f$. Dan is de monische grootste gemene deler van $p$ en $f$ dus $1$, en bestaan er volgens \ref{st:mult} polynomen $s, t\in L[x]$ zodat $1=s\cdot p+t\cdot f$. Omdat $p$ een deler is van $f\cdot g$ is er ook een $h\in L[x]$ met $p\cdot h=f\cdot g$. Maar bij elkaar geeft dat $$g=g\cdot 1=g\cdot (s\cdot p+t\cdot f)=s\cdot p\cdot g+ t\cdot f\cdot g=s\cdot p\cdot g+t\cdot p\cdot h =p\cdot (s\cdot g+t\cdot h),$$ dus $p$ deelt $g$. \begin{thm}\label{st:for}Elk monisch polynoom $f\in L[x]$ over een lichaam is te schrijven als product van positieve machten van monische, irreducibele polynomen uit $L[x]$ zijn; deze schrijf\-wijze is uniek op volgorde van de factoren na. \end{thm} \noindent {\bf Bewijs.} Dat elke monische $f$ een ontbinding als product van monisch irreducibele factoren heeft kan met inductie (naar de graad $m$ van) $f$ bewezen worden. Elke $f\in L[x]$ van graad 1 is irreducibel. Is $f$ met $\deg f=m>1$ zelf irreducibel, dan zijn we klaar, en anders zijn er $g, h\in L[x]$ zodat $f=g\cdot h$, die beide graad kleiner dan $m$ hebben en dus op grond van de inductiehypothese als product van irreducibele polynomen te schrijven zijn. Hun product geeft dan zo'n ontbinding voor $f$, die na het bij elkaar nemen van gelijke irreducibele factoren een product als in de Stelling geeft. De eenduidigheid hiervan is als volgt in te zien: veronderstel dat er twee ontbindingen $p_1p_2\cdots p_k=q_1q_2\cdots q_l$ voor $f$ zijn, met alle $p_i, q_j$ monisch en irreducibel. Dan deelt $p_1$ het product van de $q_j$, en dus op grond van het voorafgaande lemma (herhaald toegepast) tenminste \'e\'en der $q_j$, zeg $q_1$. Maar $q_1$ is irreducibel en monisch evenals $p_1$, dus $p_1=q_1$. Nu is $p_1(p_2\cdots p_k-q_2\cdots q_l)=0$, dus $p_2\cdots p_k=q_2\cdots q_l$, en we kunnen hetzelfde argument herhalen. Uiteindelijk vinden we dan dat $k=l$ en (eventueel na hernummering van de $q_j$) dat $p_i=q_i$ voor $1\leq i\leq k$. Hetgeen te bewijzen was. \opgave{Opgave}{Wat gaat er fout in de stelling als we `monisch' weglaten?} \begin{opn}\rm De stelling geeft het beoogde analogon van priemfactorontbinding in $\Z$. Een commutatieve ring zonder nuldelers waarin elk element (op volgorde van factoren en vermenigvuldiging met eenheden na) uniek als product van irreducibele elementen geschreven kan worden heet een {\it factorontbindingsring}. We weten nu dat $\Z$ en $L[x]$ (voor elk lichaam $L$) een factorontbindingsring is. Algemener geldt zelfs dat $R[x]$ een factorontbindingsring is als $R$ het zelf is; dus geldt bijvoorbeeld ook in $\Z[x]$ eenduidige priemfactorontbinding. Maar het algemene bewijs is iets lastiger. Om de stelling te gebruiken zouden we nog graag willen kunnen herkennen wat de irreducibele polynomen zijn in $L[x]$; maar dat hangt sterk af van het lichaam $L$. De reden dat het lichaam der complexe getallen $\C$ zo'n belangrijke rol speelt is gelegen in het feit (zoals uitgedrukt in de volgende stelling) dat het {\it algebra\"\i sch afgesloten} is: elke algebra\"\i sche vergelijking over $\C$ heeft een oplossing! We bewijzen deze stelling hier niet. \end{opn} \begin{thm}[Hoofdstelling van de Algebra]\label{st:falg} Als $f\in\C[x]$ en $\deg f\neq 0$ dan is er een $z\in\C$ zodat $f(z)=0$. \end{thm} \begin{gev} Als $f$ een monisch polynoom is dan geldt: \begin{hwitemize} \item $f\in\C[x]$ is irreducibel $\iff$ $\deg f=1$; \item $f\in\R[x]$ is irreducibel $\iff$ $\deg f=1$ of $f=x^2+bx+c$ met $b^2-4c<0$. \end{hwitemize} \end{gev} \medskip\noindent {\bf Bewijs.} Als $f\in\C[x]$ graad groter dan $1$ heeft, is er een ontbinding van $f$ van de vorm $f=(x-z)\cdot g$ op grond van \ref{st:zerofact} en \ref{st:falg}, en dus is $f$ reducibel. Bovendien is over een willekeurig lichaam elk polynoom van graad 1 irreducibel. Als $f\in \R[x]$ en er is een $r\in\R$ met $f(r)=0$, dan is, net als boven, $f$ reducibel tenzij $f$ van graad $1$ is. Maar zo'n $r$ bestaat niet altijd; w\'el is er altijd een $z\in\C$ met $f(z)=0$. Neem nu dus aan dat zo'n $z\in\C$ bestaat met $z\notin\R$; vanwege opgave 32 is dan ook $f(\bar z)=0$. Dan moet $f$ deelbaar zijn door $g=(x-z)(x-\bar z)=x^2-(z+\bar z)x+z\bar z$. Omdat zowel $b=-(z+\bar z)\in\R$ als $c=z\bar z\in\R$, is $g\in\R[x]$. Maar $g\mid f$ en $f$ is irreducibel in $\R[x]$, dus $f=g$ en $g$ is irreducibel. Bovendien is $b^2-4c=(z+\bar z)^2-4z\bar z=(z-\bar z)^2<0$. \opgave{Opgave}{Bewijs dat $(z-\bar z)^2\leq 0$ geldt voor alle $z\in\C$, en dat geldt $(z-\bar z)^2=0\iff z\in\R$.} \begin{opn}\rm Voor een monisch kwadratisch polynoom $f=x^2+bx+c$ geeft de {\it wortelformule} natuurlijk altijd de twee nulpunten $-b\pm\sqrt{b^2-4c}$ en ook daaraan zie je dat $f$ reducibel is over $\R$ als $b^2-4c\geq 0$. Een ander direkt gevolg van \ref{st:falg} is dat elk polynoom $f\in\C[x]$ precies $m=\deg f$ nulpunten heeft, mits we een nulpunt $z$ precies $k$ maal tellen als $(x-z)^k$ een deler is van $f$ maar $(x-z)^{k+1}$ niet. We noemen deze $k$ de {\it multipliciteit} van het nulpunt $z$. Over $\Q$ bestaan monisch irreducibele polynomen van willekeurige graad $m\geq 1$; de polynomen $x^m-2$ zijn bijvoorbeeld irreducibel in $\Q[x]$, voor elke $m\geq 1$, maar we hebben nog niet de hulpmiddelen om dat hier te bewijzen. Er volgt uit dat de rationale machten $2^{k/m}=\root m \of 2^k$ van $2$ voor $1\leq k1$ opgedeeld worden in equivalentieklassen $\bar a=\{ b\in\Z\colon b\equiv a\bmod m\}$, waar $b\equiv a\bmod m$ niets anders betekende dan: $m$ deelt $b-a$; nog anders gezegd: de deling van $b$ door $m$ heeft dezelfde rest als die van $a$. Omdat we in $L[x]$ ook deling met rest kunnen toepassen, krijgen we op een zelfde manier de volgende definitie. \begin{dfn}\rm De {\it restklassenring} $L[x]/f$, voor een $f\in L[x]$ met $\deg f>0$, bestaat uit de verzameling equivalentieklassen $$\bar g =\{ h\in L[x]\ \colon\ h\equiv g\bmod f\}=\{ g+t f\ \colon\ t\in L[x]\}$$ (waar $h\equiv g\bmod f$ dan en slechts dan als $f$ een deler is van $h-g$), voorzien van optelling en vermenigvuldiging, gegeven door: $\bar g+\bar h=\overline{g+h}$ en $\bar g\cdot \bar h=\overline{g\cdot h}$. \end{dfn} \opgave{Opgave}{Bewijs dat in $L[x]/f$ geldt: $h\in\bar g$ dan en slechts dan als bij deling met rest geldt $g=q_gf+r$ en $h=q_hf+r$, met dezelfde rest $r$.} \opgave{Opgave}{Ga na dat $L[x]/f$ zo een commutatieve ring met $1$ vormt.} \begin{thm}$L[x]/f$ is een lichaam dan en slechts dan als $f$ irreducibel is in $L[x]$. \end{thm} \medskip\noindent {\bf Bewijs.} Veronderstel dat $f$ reducibel is, dus $f=g\cdot h$ met $\deg g<\deg f$ en $\deg h< \deg f$. Dan is $f$ geen deler van $g$ of $h$, maar wel van $g\cdot h$; dus is $g\neq 0\in L[x]/f$ en $h\neq 0\in L[x]/f$ maar $g\cdot h=0\in L[x]/f$, zodat $g, h$ nuldelers zijn, en $L[x]/f$ geen lichaam kan zijn. Dat bewijst de implicatie $\Rightarrow$. Veronderstel nu dat $f$ irreducibel is, en laat $g\in L[x]$ niet deelbaar zijn door $f$. Dan is de monische grootste gemene deler van $f$ en $g$ gelijk aan $1$, dus bestaan er volgens \ref{st:mult} polynomen $s, t\in L[x]$ zodat $s\cdot f+t\cdot g=1$, oftewel $t\cdot g=1+s\cdot f$: dat betekent dat $\bar t\bar g=\bar 1\in L[x]/f$. Bij het willekeurige element $g\in L[x]$ met $\bar g\neq \bar 0$ vonden we dus een $t\in L[x]$ zodat $\bar t=\bar g^{-1}$. Elk niet-nul element in $L[x]/f$ is kennelijk inverteerbaar: de ring $L[x]/f$ is een lichaam. \begin{opn}\rm De voorgaande stelling geeft aan hoe {\it lichaamsuitbreidingen} gemaakt kunnen worden: begin met een lichaam $L$ en vind een irreducibel polynoom $f\in L[x]$, dan is $K=L[x]/f$ een lichaam. Bijvoorbeeld met $L=\Q$ en $f=x^2-2$ vinden we $K=L[x]/(x^2-2)$, een lichaam dat bestaat uit elementen $a+b\sqrt{2}$, met $a, b\in\Q$, waar $a+b\sqrt{2}$ en $c+d\sqrt{2}$ opgeteld worden volgens $$(a+b\sqrt{2})+(c+d\sqrt{2})=(a+c)+(b+d)\sqrt{2},$$ en vermenigvuldigd via $$(a+b\sqrt{2})\times (c+d\sqrt{2})=(ac+2bd)+(ad+bc)\sqrt{2},$$ (werk de haakjes uit en gebruik dat $(\sqrt{2})^2=2$). Dit lichaam $L$ geven we aan met $\Q[\sqrt{2}]$. Als $L$ het lichaam van $p$ elementen is, kunnen we zo een lichaam met $p^n$ elementen construeren door een monisch irreducibel polynoom van graad $n$ over $L$ te vinden. Later zal blijken dat we voor elke $p$ en elke $n\geq 2$ zo'n polynoom kunnen vinden. \end{opn} \opgave{Opgave}{Vind een irreducibel polynoom van graad $2$ over $\F_3$, schrijf alle elementen op van een lichaam van 9 elementen, inclusief een tabel die bij elk tweetal hun product geeft.} \opgave{Opgave}{Bewijs dat als $R$ een ring zonder nuldelers is, de enige eenheden van $R[x]$ de eenheden van $R$ zijn.} \opgave{Opgave}{Bepaal de monische grootste gemene deler $d$ en multiplicatoren $s, t$ zodanig dat $sf+tg=d$ voor: \begin{hwitemize} \item $f=x^3+1$, $g=x^5+1$; \item $f=x^5+2x^4+3x^3+5x^2-3$, $g=x^4+x^2-6$. \end{hwitemize}} \vskip-20pt \opgave{Opgave}{Ontbind de volgende polynomen in irreducibele factoren in $\Q[x]$, in $\R[x]$ en in $\C[x]$: \begin{hwitemize} \item $x^4-2$; \item $x^8-1$. \end{hwitemize}} \vskip-20pt \opgave{Opgave}{Ontbind de polynomen $x^3-1$ en $x^5-x$ in $\F_5[x]$ in irreducibele factoren.} \opgave{Opgave}{Laat $L$ een lichaam zijn en $f\in L[x]$ met $\deg f=3$. Bewijs: $f$ is reducibel dan en slechts dan als $f$ een nulpunt in $L$ heeft.} \opgave{Opgave}{Bewijs dat met $\alpha={-1+\sqrt{-3}\over 2}\in\C$ de verzameling $\Z[\alpha]=\{ a+b\alpha\ \colon\ a,b\in\Z \}$ een ring vormt (met de gewone optelling en vermenigvuldiging). Teken de deelverzameling $\Z[\alpha]\subset\C$.} \opgave{Opgave}{Geef twee elementen $f, g$ in $\Z[x]$ met grootste gemene deler $1$, waarvoor g\'e\'en elementen $s, t\in\Z[x]$ bestaan met $sf+tg=1$.}