\documentclass[11pt]{article}
\usepackage{german,a4,psfig,amssymb,ifthen,epsfig}

\parindent0em
\parskip2ex plus 0.5ex minus 0.5ex

\renewcommand{\thesection}{\arabic{section}.}

\newenvironment{algorithmus}[3]{\topsep0ex\itemsep0ex\begin{trivlist}\parskip0ex\item[]{\bf
      Algorithmus} #1 \item[] {\rm Eingabe:} #2 \item[] {\rm Ausgabe:} #3 \end{trivlist}}{}
\newtheorem{aufgabe}{Aufgabe}
\renewcommand{\theaufgabe}{\arabic{aufgabe}}

\newcommand{\dummy}[1]{}
\newcommand{\Aufg}[3]{\begin{aufgabe}[#1]\hfill #2 #3 \end{aufgabe}}

%\newcommand{\Loes}[4]{\newcommand{#1}{\subsection*{L"osungsvorschlag #3}\addcontentsline{toc}{subsubsection}{mit L"osung ({\tt #2})}#4}\dummy{#1}}
%\newcommand{\Kat}[1]{}

\newcommand{\Titel}{Computeralgebra I, WS~1997/98\\ Klausur (Scheinkriterium)}
\newcommand{\Autor}{Joachim von zur Gathen, Sandra Feisel, Michael N"ocker}

\newcommand{\romanenum}{\renewcommand{\labelenumi}{\roman{enumi}.}}

\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Q}{\mathbb Q}
\newcommand{\R}{\mathbb R}
\newcommand{\C}{\mathbb C}
\newcommand{\F}{\mathbb F}

\newcommand{\M}{{\sf M}}

\pagestyle{empty}

\begin{document}

\begin{center}
\section*{\Titel}
{\sc \Autor} \\
\medskip
Samstag, 14.2.1998, 9.00 - 12.00 Uhr, H"orsaal C1
\end{center}

%{\bf Bitte beachten:} Die Klausur ist eigenst"andig zu bearbeiten. Versucht der/die Kandidat/in, das Ergebnis seiner/ihrer Klausur durch T"auschung, z.~B. Benutzung nicht zugelassener Hilfsmittel, zu beeinflussen, wird die Klausur mit 0 Punkten bewertet. Das gilt auch, wenn die T"auschung erst nach Abgabe der Klausur festgestellt wird.

\setcounter{equation}{0}
\setcounter{figure}{0}

%\Aufg{Die Eulersche $\varphi$-Funktion}{( Punkte)}{
%
%Es ist  $\Z_n=\Z/n\Z$ ein Ring mit $n$ Elementen. $\Z_n^\times=\{a\bmod n\colon\mbox{\rm ggT}(a,n)=1\}$ ist die Menge der Einheiten von $\Z_n$. Wir definieren $\varphi(n)$ als $\varphi(n)=\#\Z^\times=\#\{a\in\Z_n\colon 0\leq a<n\mbox{ und }\mbox{\rm ggT}(a,n)=1\}$.
%
%\begin{enumerate}\romanenum
%\item Zeige: $\Z_n^\times$ ist eine multiplikative Gruppe.
%\item Beweise, da"s $\varphi(n)=n-1$ gilt, falls $n$ eine Primzahl ist.
%\item Sei nun $p$ eine Primzahl, $d\in\N$ und $n=p^d$ eine Primpotenz. Zeige, da"s $\varphi(n)=p^{d-1}(p-1)$ gilt.
%\item Zeige, da"s f"ur teilerfremde $m,n\in\N$ gilt: $\varphi(mn)=\varphi(m)\cdot\varphi(n)$. (Hinweis: Chinesischer Restsatz)
%\item Sei nun $n=p_1^{e_1}\cdots p_r^{e_r}$ die Primfaktorzerlegung von $n$, wobei $p_1,\ldots,p_r\in\N$ paarweise verschiedene Primzahlen sind. Es gelte $e_1,\ldots,e_r\in\N_{>0}$. Beweise, da"s
%$$\varphi(n)=p_1^{e_1-1}(p_1-1)\cdots p_r^{e_r-1}(p_r-1)=n\prod_{1\leq i\leq r}\left(1-\frac{1}{p_i}\right)$$
%gilt.
%\end{enumerate}
%

\Aufg{Chinesischer Restsatz}{(6+6 Punkte)}{

\begin{enumerate}\romanenum
\item Sei $R$ ein Euklidischer Ring und $a,b,c\in R$. Zeige:
\begin{enumerate}
\item[(a)] Die Kongruenz $ay\equiv b\bmod c$ hat genau dann eine L"osung $y\in R$, wenn $g=\mbox{\rm ggT}(a,c)$ ein Teiler von $b$ ist. 
\item[(b)] Falls $ay\equiv b\bmod c$ eine L"osung $y\in R$ hat, so ist die Kongruenz "aquivalent zu $(a/g)y\equiv(b/g)\bmod(c/g)$. 
\end{enumerate}
\item Sei $R=\F_5[x]$. Berechne eine L"osung $f\in\F_5[x]$ des Kongruenzensystems
\begin{eqnarray*}
f&\equiv&-1\bmod x+1\\
(x+1)f&\equiv&x+1\bmod x^3+1
\end{eqnarray*}
mit $\deg{f}<3$. (Hinweis: Bringe zuerst die zweite Kongruenz in die Form $f\equiv v\bmod m$ f"ur geeignete $v,m\in\F_5[x]$.)
\end{enumerate}
}

\Aufg{Blockweise Polynomarithmetik}{(8+4 Punkte)}{

Seien $n,k\in\N$ und $F$ ein K"orper. ${\sf M}(n)$ bezeichne die Anzahl Operationen in $F$, die ben"otigt werden, um zwei Polynome "uber $F$ vom Grad kleiner $n$ zu multiplizieren. Seien $f,g\in F[x]$ mit $\deg{f}=kn-1$ und $\deg{g}=n-1$.

\begin{enumerate}\romanenum
\item Zeige: $f\cdot g\in F[x]$ kann mit $k{\sf M}(n)+O(kn)$ Operationen in $ F$ berechnet werden. (Hinweis: teile $f$ in Bl"ocke vom Grad $<n$.)
\item Eine direkte Absch"atzung f"ur die Multiplikation von $f$ und $g$ liefert f"ur die Kosten die bekannte Schranke ${\sf M}(kn)$. Vergleiche diese mit der in i. gefundenen Kostenabsch"atzung. Unterscheide dabei nach klassischer Polynommultiplikation, Polynommultiplikation nach Karazuba und Polynommultiplikation mittels FFT (dabei sei angenommen, da"s $F$ die FFT unterst"utzt).
%, indem Du die Werte f"ur ${\sf M}(n)$ einsetzt, die sich ergeben bei 
%\begin{enumerate}
%\item[a)] klassischer Multiplikation,
%\item[b)] Polynommultiplikation nach Karazuba,
%\item[c)] Polynommultiplikation mittels FFT, wobei angenommen werden kann, da"s $F$ die FFT unterst"utzt.
%\end{enumerate}
\end{enumerate}
}

%\Aufg{(A1:) Primitive Einheitswurzel}{(2+6+10 Punkte)}{
%
%Seien $p$ eine Primzahl und $\Z_p=\Z/p\Z$ der K"orper mit $p$ Elementen. $\alpha\in\Z_p$ sei ein erzeugendes Element der multiplikativen Gruppe $\Z_p^\times$.
%\begin{enumerate}\romanenum
%\item Seien $0<k< p$ und $d=(p-1)/\mbox{\rm ggT}(p-1,k)$. Zeige: $\omega=\alpha^k\in\Z_p^\times$ ist eine primitive $d$-te Einheitswurzel in $\Z_p$.
%\item Weise nach, da"s $3$ ein erzeugendes Element von $\Z_{17}^\times$ ist. Bestimme damit alle vierten primitiven Einheitswurzeln in $\Z_{17}$. Begr"unde, warum es keine weiteren gibt.
%\item Es gilt $83521=17^4$. Berechne aus den Ergebnissen von ii. mit Hilfe der Newton-Iteration alle primitiven vierten Einheitswurzeln in $\Z_{83521}$. Begr"unde, warum es keine weiteren gibt. 
%\end{enumerate}
%}


\Aufg{Nullstellen per Newton-Iteration}{(2+8+2 Punkte)}{

Es ist $\varphi=x^3-17x^2+57x-210\in\Z[x]$.
\begin{enumerate}\romanenum
\item Bestimme alle Nullstellen von $\varphi\bmod 7$ in $\Z_7$.
\item Finde mittels $7$-adischer Newton-Iteration alle Nullstellen von $\varphi\bmod 7^4$.
\item Bestimme aus dem Ergebnis von ii. alle ganzzahligen Nullstellen von $\varphi$ und begr"unde, warum es keine weiteren ganzzahligen Nullstellen gibt.
\end{enumerate}
}

%\Aufg{(A2:) Primitive Einheitswurzeln}{(4+8 Punkte)}{
%
%Seien $p,q\in\N$ zwei Primzahlen. Auf dem Produktring $\Z_p\times\Z_q$ sind die Verkn"upfungen $+$ und $\cdot$ komponentenweise definiert: $(a,b)+(c,d)=(a+c,b+d)$ und $(a,b)\cdot(c,d)=(a\cdot c,b\cdot d)$ f"ur $a,c\in\Z_p$ und $b,d\in\Z_q$. Mit diesen Verkn"upfungen ist $\Z_p\times\Z_q$ ein Ring mit Nullelement $(0,0)$ und Einselement $(1,1)$.
%\begin{enumerate}\romanenum
%\item Zeige: $N=\{(a,0)\colon a\in\Z_p^\times\}\cup\{(0,b)\colon b\in\Z_q^\times\}$ ist die Menge aller Nullteiler von $\Z_p\times\Z_q$.
%\item Zeige: $(a,b)\in\Z_p\times\Z_q$ ist eine primitive $n$-te Einheitswurzel in $\Z_p\times\Z_q$ genau dann, wenn $a$ eine primitive $n$-te Einheitswurzel in $\Z_p$ und $b$ eine primitive $n$-te Einheitswurzel in $\Z_q$ ist.
%\end{enumerate}
%}


\Aufg{Primitive Einheitswurzeln}{(2+2+8 Punkte)}{

\begin{enumerate}\romanenum
\item Sei $F$ ein K"orper und $\omega\in F$ eine primitive vierte Einheitswurzel. Zeige: Dann ist auch $-\omega\in F$ eine primitive vierte Einheitswurzel in $F$. Begr"unde, warum es keine weiteren primitiven vierten Einheitswurzeln in $F$ gibt.
\item Zeige: $\alpha=5$ ist eine primitive vierte Einheitswurzel in $\Z_{13}$ und $\beta=4$ ist eine primitive vierte Einheitswurzel in $\Z_{17}$.
\item Bestimme die Menge aller primitiven vierten Einheitswurzeln in $\Z_{13}\times\Z_{17}$. 
\end{enumerate}

{\bf Hinweis:} Seien $p,q\in\N$ Primzahlen. Auf dem Produktring $\Z_p\times\Z_q$ sind die Verkn"upfungen $+$ und $\cdot$ komponentenweise definiert: $(a,b)+(c,d)=(a+c,b+d)$ und $(a,b)\cdot(c,d)=(a\cdot c,b\cdot d)$ f"ur $a,c\in\Z_p$ und $b,d\in\Z_q$. Mit diesen Verkn"upfungen ist $\Z_p\times\Z_q$ ein Ring mit Nullelement $(0,0)$ und Einselement $(1,1)$.
}


\Aufg{Resultanten}{(6 Punkte)}{

Seien $\alpha\in\R$ ein Parameter und $f,g_{\alpha}\in\R[x]$. Es gelte $\mbox{\rm res}(f,g_{\alpha})=\alpha^3+\alpha^2+\alpha+1$. Bestimme alle $\alpha\in\R$, f"ur die gilt: $\mbox{\rm ggT}(f,g_{\alpha})\neq1$.
}
\end{document}