m_{2}$ (denn $m_{1}$ und $m_{2}$ sind verschieden), also $m_{1}-m_{2}>0$. Andererseits ist $m_{1}% -\underbrace{m_{2}}_{\geq0}\leq m_{1}
0$), aber bis man es gefunden hat, muss man im schlimmsten Fall ungef\"{a}hr $\dfrac{n-1}{n}p^{n}$ Polynome vergeblich auf Irreduzibilit\"{a}t \"{u}berpr\"{u}fen. Und auch wenn man ein irreduzibles Polynom findet, hat es etwas Willk\"{u}rliches - man h\"{a}tte genauso gut auf eins der $\dfrac{1}{n}\sum\limits_{d\mid n}\mu\left( d\right) p^{n\diagup d}-1$ anderen monischen irreduziblen Polynome sto\ss en k\"{o}nnen. Man kann also theoretisch einen K\"{o}rper mit $q$ Elementen konstruieren, aber diese Konstruktion kann sehr lange dauern und das Ergebnis h\"{a}ngt davon ab, in welcher Reihenfolge man die Polynome nach einem irreduziblen durchsucht (obwohl alle K\"{o}rper mit $q$ Elementen letztendlich zueinander isomorph sind). Wenn man in der Praxis einen K\"{o}rper mit $q$ Elementen \textit{f\"{u}r festes }$q$ n\"{o}tig hat\footnote{Und dies hat man sehr h\"{a}ufig in Kodierungstheorie und Kryptographie.}, verwendet man daher fast nie allgemeine Algorithmen zu seiner Konstruktion, sondern nimmt vorgefertigte Additions- und Multiplikationstabellen. \subsection{Die Anzahl aller monischen irreduziblen Polynome \"{u}ber $F$} Nun der Hauptsatz dieses Abschnitts: \begin{quote} \textbf{Satz 8.3:} Sei $F$ ein K\"{o}rper mit endlich vielen Elementen. F\"{u}r jedes $n\in\mathbb{N}$ gibt es dann genau $\dfrac{1}{n}\sum \limits_{d\mid n}\mu\left( d\right) \left\vert F\right\vert ^{n\diagup d}$ monische irreduzible Polynome in $F\left[ X\right] $ vom Grad $n$. \end{quote} Der Beweis dieses Satzes f\"{u}hrt uns \"{u}ber einen Umweg zum Ziel. Zuerst einmal m\"{u}ssen wir die irreduziblen Faktoren des Polynoms $X^{q^{n}}-X$ (wobei $q=\left\vert F\right\vert $) betrachten: \begin{quote} \textbf{Satz 8.4:} Sei $F$ ein K\"{o}rper mit endlich vielen Elementen. Sei $q=\left\vert F\right\vert $. Sei $n\in\mathbb{N}$. Ist $Q\in F\left[ X\right] $ ein irreduzibles Polynom mit $Q\mid X^{q^{n}}-X$, dann ist $\deg Q\mid n$. \textbf{Satz 8.5:} Sei $F$ ein K\"{o}rper mit endlich vielen Elementen. Sei $q=\left\vert F\right\vert $. Sei $n\in\mathbb{N}$. Ist $Q\in F\left[ X\right] $ ein irreduzibles Polynom mit $\deg Q\mid n$, dann ist $Q\mid X^{q^{n}}-X$. \textbf{Satz 8.6:} Sei $F$ ein K\"{o}rper mit endlich vielen Elementen. Sei $q=\left\vert F\right\vert $. Sei $n\in\mathbb{N}$. Ist $Q\in F\left[ X\right] $ ein Polynom mit $Q^{2}\mid X^{q^{n}}-X$, dann ist $\deg Q=0$. \textbf{Satz 8.7:} Sei $F$ ein K\"{o}rper mit endlich vielen Elementen. Sei $q=\left\vert F\right\vert $. F\"{u}r jedes $d\in\mathbb{N}$ sei $\operatorname*{Irr}\nolimits_{d}$ die Menge aller monischen irreduziblen Polynome $Q\in F\left[ X\right] $, die $\deg Q=d$ erf\"{u}llen. F\"{u}r jedes $n\in\mathbb{N}$ gilt dann% \[ X^{q^{n}}-X=\prod\limits_{d\mid n}\prod\limits_{Q\in\operatorname*{Irr}% \nolimits_{d}}Q. \] \end{quote} Diese S\"{a}tze werden wir alle im n\"{a}chsten Abschnitt zeigen. Zuerst jedoch wollen wir sehen, wie Satz 8.3 aus ihnen folgt: \textit{Beweis von Satz 8.3:} Sei $q=\left\vert F\right\vert $. Wir erinnern uns an die Definitionen des Begriffs "Dirichlet-Faltung" aus Abschnitt 2.4. Wir betrachten $n\in\mathbb{N}$ nicht als vorgegeben, sondern als variabel. F\"{u}r jedes $d\in\mathbb{N}$ sei $\operatorname*{Irr}\nolimits_{d}$ die Menge aller monischen irreduziblen Polynome $Q\in F\left[ X\right] $, die $\deg Q=d$ erf\"{u}llen. Wir definieren eine Zahlenfunktion $\tau :\mathbb{N}_{+}\rightarrow\mathbb{Z}$ durch% \[ \left( \tau\left( d\right) =\left\vert \operatorname*{Irr}\nolimits_{d}% \right\vert \cdot d\text{ f\"{u}r alle }d\in\mathbb{N}_{+}\right) . \] Wir werden nun zeigen, da\ss \ $\left( \tau\ast\underline{1}\right) \left( n\right) =q^{n}$ f\"{u}r alle $n\in\mathbb{N}_{+}$ gilt. Dazu definieren wir eine weitere Zahlenfunktion $\mathfrak{f}:\mathbb{N}_{+}\rightarrow\mathbb{Z}$ durch% \[ \left( \mathfrak{f}\left( n\right) =q^{n}\text{ f\"{u}r alle }% n\in\mathbb{N}_{+}\right) . \] Jetzt beweisen wir, da\ss \ $\mathfrak{f}=\tau\ast\underline{1}$ gilt. F\"{u}r jedes $n\in\mathbb{N}$ ist% \begin{align*} \mathfrak{f}\left( n\right) & =q^{n}=\deg\left( X^{q^{n}}-X\right) =\deg\left( \prod\limits_{d\mid n}\prod\limits_{Q\in\operatorname*{Irr}% \nolimits_{d}}Q\right) \ \ \ \ \ \ \ \ \ \ \left( \text{nach Satz 8.7}\right) \\ & =\sum\limits_{d\mid n}\sum\limits_{Q\in\operatorname*{Irr}\nolimits_{d}% }\underbrace{\deg Q}_{=d\text{, denn }Q\in\operatorname*{Irr}\nolimits_{d}}\\ & \ \ \ \ \ \ \ \ \ \ \left( \begin{array} [c]{c}% \text{denn \"{u}ber einem K\"{o}rper ist der Grad eines Produktes von}\\ \text{Polynomen gleich der Summe der Grade dieser Polynome}% \end{array} \right) \\ & =\sum\limits_{d\mid n}\underbrace{\sum\limits_{Q\in\operatorname*{Irr}% \nolimits_{d}}d}_{=\left\vert \operatorname*{Irr}\nolimits_{d}\right\vert \cdot d}=\sum\limits_{d\mid n}\underbrace{\left\vert \operatorname*{Irr}% \nolimits_{d}\right\vert \cdot d}_{=\tau\left( d\right) }=\sum\limits_{d\mid n}\tau\left( d\right) , \end{align*} und nach der Definition der Dirichlet-Faltung ist $\left( \tau\ast \underline{1}\right) \left( n\right) =\sum\limits_{d\mid n}\tau\left( d\right) \underbrace{\underline{1}\left( \dfrac{n}{d}\right) }_{=1}% =\sum\limits_{d\mid n}\tau\left( d\right) $, also $\mathfrak{f}\left( n\right) =\left( \tau\ast\underline{1}\right) \left( n\right) $. Daraus folgt $\mathfrak{f}=\tau\ast\underline{1}=\underline{1}\ast\tau$ (da die Dirichlet-Faltung $\ast$ kommutativ ist). Dies f\"{u}hrt wiederum auf% \begin{align*} \mu\ast\mathfrak{f} & =\mu\ast\left( \underline{1}\ast\tau\right) =\left( \mu\ast\underline{1}\right) \ast\tau\ \ \ \ \ \ \ \ \ \ \left( \text{denn die Dirichlet-Faltung }\ast\text{ ist assoziativ}\right) \\ & =\varepsilon\ast\tau\ \ \ \ \ \ \ \ \ \ \left( \text{denn }\mu \ast\underline{1}=\varepsilon\text{ nach Satz 2.4 \textbf{(b)}}\right) \\ & =\tau\ \ \ \ \ \ \ \ \ \ \left( \text{denn }\varepsilon\ast f=f\text{ f\"{u}r jede Zahlenfunktion }f\right) . \end{align*} F\"{u}r jedes $n\in\mathbb{N}$ ist also $\left( \mu\ast\mathfrak{f}\right) \left( n\right) =\tau\left( n\right) $. Da $\left( \mu\ast\mathfrak{f}% \right) \left( n\right) =\sum\limits_{d\mid n}\mu\left( d\right) \mathfrak{f}\left( \dfrac{n}{d}\right) $ (nach der Definition der Dirichlet-Faltung) und $\tau\left( n\right) =\left\vert \operatorname*{Irr}% \nolimits_{n}\right\vert \cdot n$ ist (gem\"{a}\ss \ der Definition von $\tau $), bedeutet dies $\sum\limits_{d\mid n}\mu\left( d\right) \mathfrak{f}% \left( \dfrac{n}{d}\right) =\left\vert \operatorname*{Irr}\nolimits_{n}% \right\vert \cdot n$, also% \[ \left\vert \operatorname*{Irr}\nolimits_{n}\right\vert =\dfrac{1}{n}% \sum\limits_{d\mid n}\mu\left( d\right) \mathfrak{f}\left( \dfrac{n}% {d}\right) =\dfrac{1}{n}\sum\limits_{d\mid n}\mu\left( d\right) \left\vert F\right\vert ^{n\diagup d}% \] (denn nach der Definition von $\mathfrak{f}$ ist $\mathfrak{f}\left( \dfrac{n}{d}\right) =q^{n\diagup d}=\left\vert F\right\vert ^{n\diagup d}$). Nun ist aber $\operatorname*{Irr}\nolimits_{n}$ definiert als die Menge aller monischen irreduziblen Polynome $Q\in F\left[ X\right] $, die $\deg Q=n$ erf\"{u}llen. Folglich ist $\left\vert \operatorname*{Irr}\nolimits_{n}% \right\vert $ die Anzahl aller monischen irreduziblen Polynome $Q\in F\left[ X\right] $, die $\deg Q=n$ erf\"{u}llen. Das hei\ss t, $\left\vert \operatorname*{Irr}\nolimits_{n}\right\vert $ ist die Anzahl aller monischen irreduziblen Polynome $Q\in F\left[ X\right] $ vom Grad $n$. Aus $\left\vert \operatorname*{Irr}\nolimits_{n}\right\vert =\dfrac{1}{n}\sum\limits_{d\mid n}\mu\left( d\right) \left\vert F\right\vert ^{n\diagup d}$ folgt also: Die Anzahl aller monischen irreduziblen Polynome $Q\in F\left[ X\right] $ vom Grad $n$ ist $\dfrac{1}{n}\sum\limits_{d\mid n}\mu\left( d\right) \left\vert F\right\vert ^{n\diagup d}$. Damit ist Satz 8.3 bewiesen. [...] \textit{Beweis von Satz 8.7:} Erstmal eine triviale Anmerkung: Die Mengen $\operatorname*{Irr}\nolimits_{d}$ f\"{u}r verschiedene $d\in\mathbb{N}$ sind paarweise disjunkt, d. h. f\"{u}r je zwei verschiedene $d\in\mathbb{N}$ und $e\in\mathbb{N}$ gilt $\operatorname*{Irr}\nolimits_{d}\cap\operatorname*{Irr}% \nolimits_{e}=\varnothing$\ \ \ \ \footnote{\textit{Beweis:} F\"{u}r jedes $P\in\operatorname*{Irr}\nolimits_{d}\cap\operatorname*{Irr}\nolimits_{e}$ gilt, da\ss \ $P$ ein irreduzibles Polynom mit $\deg P=d$ ist (da $P\in\operatorname*{Irr}\nolimits_{d}\cap\operatorname*{Irr}\nolimits_{e}% \subseteq\operatorname*{Irr}\nolimits_{d}$), und da\ss \ $P$ ein irreduzibles Polynom mit $\deg P=e$ ist (da $P\in\operatorname*{Irr}\nolimits_{d}% \cap\operatorname*{Irr}\nolimits_{e}\subseteq\operatorname*{Irr}\nolimits_{e}% $). F\"{u}r jedes $P\in\operatorname*{Irr}\nolimits_{d}\cap\operatorname*{Irr}% \nolimits_{e}$ gilt also $d=\deg P=\deg P=e$ im Widerspruch zu $d\neq e$. Somit existiert kein $P\in\operatorname*{Irr}\nolimits_{d}\cap \operatorname*{Irr}\nolimits_{e}$. Das hei\ss t, $\operatorname*{Irr}% \nolimits_{d}\cap\operatorname*{Irr}\nolimits_{e}=\varnothing$.}. Jedes Polynom $Q\in F\left[ X\right] $ hat eine Primfaktorzerlegung, d. h. eine Darstellung in der Form $Q=\beta\cdot\prod\limits_{i=1}^{M}Q_{i}$, wobei $\beta\in F$ ein K\"{o}rperelement ist, $M$ eine nat\"{u}rliche Zahl ist, und $Q_{1}$, $Q_{2}$, $...$, $Q_{M}$ monische irreduzible Polynome sind. Sei% \[ X^{q^{n}}-X=\alpha\cdot\prod\limits_{i=1}^{N}P_{i}% \] die Primfaktorzerlegung des Polynoms $X^{q^{n}}-X$, wobei $\alpha\in F$ ein K\"{o}rperelement ist, $N$ eine nat\"{u}rliche Zahl ist, und $P_{1}$, $P_{2}$, $...$, $P_{N}$ monische irreduzible Polynome sind. Da die Polynome $P_{1}$, $P_{2}$, $...$, $P_{N}$ alle monisch sind, ist $\alpha$ der Leitkoeffizient des Produktes $\alpha\cdot\prod\limits_{i=1}% ^{N}P_{i}=X^{q^{n}}-X$, und damit gleich $1$. Wir haben also $\alpha=1$, und somit wird $X^{q^{n}}-X=\alpha\cdot\prod\limits_{i=1}^{N}P_{i}$ zu $X^{q^{n}% }-X=\prod\limits_{i=1}^{N}P_{i}$. Die Polynome $P_{1}$, $P_{2}$, $...$, $P_{N}$ m\"{u}ssen paarweise verschieden sein (denn w\"{a}ren zwei von ihnen gleich, dann w\"{u}rden wir mithilfe von Satz 8.6 schnell auf einen Widerspruch sto\ss en\footnote{Hier ist der Widerspruch im Detail: W\"{a}ren zwei der Polynome $P_{1}$, $P_{2}$, $...$, $P_{N}$ gleich, d. h. g\"{a}be es zwei verschiedene Elemente $i$ und $j$ der Menge $\left\{ 1,2,...,n\right\} $ mit $P_{i}=P_{j}$, dann w\"{a}re $X^{q^{n}}-X=\prod\limits_{i=1}^{N}P_{i}$ teilbar durch $\underbrace{P_{i}% }_{=P_{j}}\cdot P_{j}=P_{j}^{2}$, was (nach Satz 8.6, angewandt auf $Q=P_{j}$) zu $\deg P_{j}=0$ f\"{u}hren w\"{u}rde, im Widerspruch dazu, da\ss \ $P_{j}$ irreduzibel ist.}). Daher kommt jedes Element der Menge $\left\{ P_{1}% ,P_{2},...,P_{N}\right\} $ im\ Produkt $\prod\limits_{i=1}^{N}P_{i}$ genau einmal vor; das hei\ss t, \[ \prod\limits_{Q\in\left\{ P_{1},P_{2},...,P_{N}\right\} }Q=\prod \limits_{i=1}^{N}P_{i}=X^{q^{n}}-X. \] Wir werden nun zeigen, da\ss \ $\left\{ P_{1},P_{2},...,P_{N}\right\} =\bigcup\limits_{d\mid n}\operatorname*{Irr}\nolimits_{d}$ ist. In der Tat gilt $\left\{ P_{1},P_{2},...,P_{N}\right\} \subseteq\bigcup\limits_{d\mid n}\operatorname*{Irr}\nolimits_{d}$, denn f\"{u}r jedes $i\in\left\{ 1,2,...,N\right\} $ ist $P_{i}\in\bigcup\limits_{d\mid n}\operatorname*{Irr}% \nolimits_{d}$\ \ \ \ \footnote{\textit{Beweis:} Es gilt $P_{i}\mid \prod\limits_{i=1}^{N}P_{i}=X^{q^{n}}-X$ und daher $\deg P_{i}\mid n$ (nach Satz 8.4, angewandt auf $Q=P_{i}$) und daher $P_{i}\in\operatorname*{Irr}% \nolimits_{\deg P_{i}}$ (nach der Definition von $\operatorname*{Irr}% \nolimits_{\deg P_{i}}$, denn $P_{i}$ ist ein monisches irreduzibles Polynom mit $\deg P_{i}=\deg P_{i}$), also $P_{i}\in\bigcup\limits_{d\mid n}\operatorname*{Irr}\nolimits_{d}$ (denn $\deg P_{i}\mid n$).}. Andererseits gilt $\bigcup\limits_{d\mid n}\operatorname*{Irr}\nolimits_{d}\subseteq \left\{ P_{1},P_{2},...,P_{N}\right\} $, denn f\"{u}r jedes $Q\in \bigcup\limits_{d\mid n}\operatorname*{Irr}\nolimits_{d}$ gilt $Q\in\left\{ P_{1},P_{2},...,P_{N}\right\} $\ \ \ \ \textit{Beweis:} Aus $Q\in\bigcup\limits_{d\mid n}\operatorname*{Irr}% \nolimits_{d}$ folgt, da\ss \ es ein $d\in\mathbb{N}$ mit $d\mid n$ gibt, das $Q\in\operatorname*{Irr}\nolimits_{d}$ erf\"{u}llt. F\"{u}r dieses $d$ mu\ss \ dann gelten, da\ss \ $Q$ irreduzibel ist und $\deg Q=d$ erf\"{u}llt (denn $Q\in\operatorname*{Irr}\nolimits_{d}$, und laut der Definition von $\operatorname*{Irr}\nolimits_{d}$ ist jedes Element $R$ von $\operatorname*{Irr}\nolimits_{d}$ irreduzibel und erf\"{u}llt $\deg R=d$). Daraus folgt $\deg Q=d\mid n$, und nach Satz 8.5 ist daher $Q\mid X^{q^{n}}% -X$. Das irreduzible Polynom $Q$ teilt also das Polynom $X^{q^{n}}% -X=\prod\limits_{i=1}^{N}P_{i}$. Laut Folgerung [...] folgt hieraus, da\ss \ es ein $i\in\left\{ 1,2,...,N\right\} $ gibt, so da\ss \ das irreduzible Polynom $Q$ das Polynom $P_{i}$ teilt. F\"{u}r dieses $i\in\left\{ 1,2,...,N\right\} $ mu\ss \ also $Q=P_{i}$ gelten (denn da $P_{i}$ selber irreduzibel ist, kann $Q$ nur dann $P_{i}$ teilen, wenn $Q=1$ oder $Q=P_{i}$ gilt, doch da $Q=1$ unm\"{o}glich ist (denn $Q$ ist irreduzibel), mu\ss \ also $Q=P_{i}$ sein). Somit ist $Q\in\left\{ P_{1},P_{2},...,P_{N}\right\} $. [insert Folgerung] [make footnote] Aus $\bigcup\limits_{d\mid n}\operatorname*{Irr}\nolimits_{d}\subseteq\left\{ P_{1},P_{2},...,P_{N}\right\} $ und $\left\{ P_{1},P_{2},...,P_{N}\right\} \subseteq\bigcup\limits_{d\mid n}\operatorname*{Irr}\nolimits_{d}$ folgt nun $\left\{ P_{1},P_{2},...,P_{N}\right\} =\bigcup\limits_{d\mid n}% \operatorname*{Irr}\nolimits_{d}$. Somit ist% \begin{align*} X^{q^{n}}-X & =\prod\limits_{Q\in\left\{ P_{1},P_{2},...,P_{N}\right\} }Q=\prod\limits_{Q\in\bigcup\limits_{d\mid n}\operatorname*{Irr}\nolimits_{d}% }Q\ \ \ \ \ \ \ \ \ \ \left( \text{da }\left\{ P_{1},P_{2},...,P_{N}% \right\} =\bigcup\limits_{d\mid n}\operatorname*{Irr}\nolimits_{d}\right) \\ & =\prod\limits_{d\mid n}\prod\limits_{Q\in\operatorname*{Irr}\nolimits_{d}% }Q. \end{align*} (denn die Mengen $\operatorname*{Irr}\nolimits_{d}$ f\"{u}r verschiedene $d\in\mathbb{N}$ sind paarweise disjunkt). Damit ist Satz 8.7 bewiesen. [...] K\"{o}rpererweiterungen einf\"{u}hren. Zuerst ein Hilfsresultat: \textbf{Satz 8.8 (der Satz von Bezout f\"{u}r Polynome):} [...] [...] Folgerung \"{u}ber $Q\mid\prod$ [...] \textit{Beweis von Satz 8.4:} Wir betrachten den Faktorring $F\left[ X\right] \diagup\left( Q\right) $. Unser ers \textit{Beweis von Satz 8.3:} Wir betrachten $n\in\mathbb{N}$ nicht als vorgegeben, sondern als variabel. Wir definieren eine Zahlenfunktion $\tau:\mathbb{N}_{+}\rightarrow\mathbb{Z}$ durch% \[ \left( \begin{array} [c]{l}% \tau\left( n\right) =\left( \text{Anzahl aller monischen irreduziblen Polynome in }F\left[ X\right] \text{ vom Grad }n\right) \\ \ \ \ \ \ \ \ \ \ \ \text{ }\ \ \ \ \ \ \ \ \ \ \text{f\"{u}r alle }% n\in\mathbb{N}_{+}% \end{array} \right) . \] Wir wollen nun zeigen, da\ss \ $\left( \tau\ast\underline{1}\right) \left( n\right) =\left\vert F\right\vert ^{n}$ f [...] wobei $\ast$ die Dirichlet-Faltung bezeichnet (f\"{u}r die Definition dieser Faltung siehe Abschnitt 2.4). [...] [existenz beweisen] * leider nur f\"{u}r $q$ primpotenz Damit haben wir eine kombinatorische (oder, in unserem Fall eher algebraische oder zahlentheoretische - denn endliche K\"{o}rper mit $q$ Elementen sind mit reiner Kombinatorik schwer zu beschreiben, au\ss er wenn $q$ Primzahl ist) Interpretation f\"{u}r die Zahlen $\dfrac{1}{n}\sum\limits_{d\mid n}\mu\left( d\right) q^{n\diagup d}$ gefunden, wenn $n\in\mathbb{N}_{+}$ und $q$ Primpotenz ist. Folglich sind diese Zahlen ganz, wenn $n\in\mathbb{N}_{+}$ und $q$ Primpotenz ist. Leider ist es nicht m\"{o}glich, hieraus zu folgern, da\ss \ sie auch f\"{u}r \textit{alle ganzen }$q$ (und nicht nur f\"{u}r Primpotenzen) ganz sind; es gibt n\"{a}mlich durchaus Polynome, die auf allen Primpotenzen ganzzahlige Werte annehmen, aber nicht auf allen ganzen Zahlen. Au\ss erdem: Auch wenn dies m\"{o}glich w\"{a}re, h\"{a}tten wir damit nur die Ganzzahligkeit von $\dfrac{1}{n}\sum\limits_{d\mid n}\mu\left( d\right) q^{n\diagup d}$ bewiesen und nicht die Ganzzahligkeit von $\dfrac{1}{n}% \sum\limits_{d\mid n}\phi\left( d\right) q^{n\diagup d}$; um letztere daraus zu folgern, m\"{u}sste man wieder das Argument bem\"{u}hen, mit dem die \"{A}quivalenz $\mathcal{F}\Longleftrightarrow\mathcal{G}$ von Satz 2.1 gezeigt wurde. ... \section{Freie Liealgebren und Dimensionen} ... \section{Wittpolynome} ... \section{Zahlentheorie II: Geisterburnsidefolgen} In Abschnitt 2 haben wir Satz 1.1 verallgemeinert, indem wir $q^{n\diagup d}$ im Term $\dfrac{1}{n}\sum\limits_{d\mid n}\phi\left( d\right) q^{n\diagup d}$ durch $b_{n\diagup d}$ ersetzt haben, wobei $\left( b_{1},b_{2}% ,b_{3},...\right) \in\mathbb{Z}^{\mathbb{N}_{+}}$ eine Folge ganzer Zahlen ist. Es ist aber auch eine andere Verallgemeinerung m\"{o}glich, indem man $q$ durch $q_{d}$ ersetzt f\"{u}r eine Folge $\left( q_{1},q_{2},q_{3}% ,...\right) \in\mathbb{Z}^{\mathbb{N}_{+}}$ ganzer Zahlen. Wieder kann man sich dann fragen, wann $\dfrac{1}{n}\sum\limits_{d\mid n}\phi\left( d\right) q_{d}^{n\diagup d}\in\mathbb{Z}$ f\"{u}r jedes $n\in\mathbb{N}_{+}$ gilt. Folgender Satz (den ich nirgendwo in der Literatur gesehen habe) gibt die Antwort: \begin{quote} \textbf{Satz 11.1 (der \"{A}quivalenzsatz f\"{u}r Geisterburnsidefolgen):} Sei $\left( q_{1},q_{2},q_{3},...\right) \in\mathbb{Z}^{\mathbb{N}_{+}}$ eine Folge ganzer Zahlen. Dann sind folgende Aussagen $\mathcal{A}% _{\operatorname{burn}}$ und $\mathcal{G}_{\operatorname{burn}}$ \"{a}quivalent: \textit{Aussage }$\mathcal{A}_{\operatorname{burn}}$\textit{:} F\"{u}r jede Zahl $n\in\mathbb{N}_{+}$ und jeden Primteiler $p$ von $n$ gilt% \[ q_{n\diagup p}\equiv q_{n}\operatorname{mod}p. \] \textit{Aussage }$\mathcal{G}_{\operatorname{burn}}$\textit{:} F\"{u}r jedes $n\in\mathbb{N}_{+}$ gilt% \[ \sum_{d\mid n}\phi\left( d\right) q_{d}^{n\diagup d}\in n\mathbb{Z}. \] \end{quote} [...] [endlicher fall vll auch] [m\"{o}bius etc] * wohl eine beweisskizze \section{Spuren von Matrixpotenzen} ... \section{Die Perlenketten-Identit\"{a}t} [...] \section{Kombinatorik III: Teilmengen von $\left\{ 1,2,...,n\right\} $ mit durch $n$ teilbarer Summe} [achtung: scheint nur \"{u}ber ungerade $d$ zu summieren] * auch durch $kn$ teilbare summe betrachten * anzahlen von elementen fixen, oder: wie kommt man an die binomialkoeffizienten http://math.stackexchange.com/questions/314788/let-p-be-an-odd-prime-number-how-many-p-element-subsets-of-1-2-3-4-ldo http://www.math.niu.edu/\symbol{126}rusin/problems-math/imo http://www.artofproblemsolving.com/Forum/viewtopic.php?p=107230 http://www.cs.cornell.edu/\symbol{126}asdas/imo/imo/isoln/isoln956.html allgemeines $p$: http://www.artofproblemsolving.com/Forum/viewtopic.php?t=308956 http://www.artofproblemsolving.com/Forum/viewtopic.php?t=300135 Exercise 1.105 in Stanleys EC1 L\"{u}becks Theorem? * stirlingnumberversion \section*{Literaturhinweise} [1] Michiel Hazewinkel, \textit{Witt vectors. Part 1}, revised version: 20 April 2008.\newline% \texttt{\href{http://arxiv.org/abs/0804.3888}{\texttt{http://arxiv.org/abs/0804.3888}% }} [2] Siegfried Bosch, \textit{Algebra}, Sechste Auflage, Springer-Verlag 2006. [3] Darij Grinberg, \textit{Witt\#5: Around the integrality criterion 9.93}.\newline% \texttt{\href{http://www.cip.ifi.lmu.de/~grinberg/algebra/witt5.pdf}{\texttt{http://www.cip.ifi.lmu.de/\symbol{126}% grinberg/algebra/witt5.pdf}}} [4] Tales et al., \textit{MathLinks topic \#30906 ("Multiplicative function")}.\newline% \texttt{\href{http://www.mathlinks.ro/Forum/viewtopic.php?t=30906}{\texttt{http://www.mathlinks.ro/Forum/viewtopic.php?t=30906}% }} [5] Reinhold Remmert, Peter Ulrich, \textit{Elementare Zahlentheorie}, 3. Auflage 2008. [6] Arthur Engel, \textit{Problem-Solving Strategies}, Springer 1998. [7] Xenon et al., \textit{Matheplanet topic \#130535.}\newline% \texttt{\href{http://matheplanet.com/matheplanet/nuke/html/viewtopic.php?topic=130535}{\texttt{http://matheplanet.com/matheplanet/nuke/html/viewtopic.php?topic=130535}% }} [8] Herbert S. Wilf, \textit{generatingfunctionology}, 2004.\newline% \texttt{\href{http://www.math.upenn.edu/~wilf/DownldGF.html}{\texttt{http://www.math.upenn.edu/\symbol{126}% wilf/DownldGF.html}}} [9] Serge Lang, \textit{Algebra}, Third Edition, Springer 2002. [10] Pierre Antoine Grillet, \textit{Abstract Algebra}, Second Edition, Springer 2007. [11] Nicolas Bourbaki, \textit{Algebra I, Chapters 1-3}, 2nd printing, Springer 1989. [12] Darij Grinberg, \textit{Witt\#4: Some computations with symmetric functions}.\newline% \texttt{\href{http://www.cip.ifi.lmu.de/~grinberg/algebra/witt4.pdf}{\texttt{http://www.cip.ifi.lmu.de/\symbol{126}% grinberg/algebra/witt4.pdf}}} [13] Ronald L. Graham, Donald E. Knuth, Oren Patashnik, \textit{Concrete Mathematics}, 2nd Edition, 1994. [14] \textit{Sum of binomial coefficients [with gcd] (MathLinks topic \#91364)},\newline% \texttt{\href{http://www.mathlinks.ro/Forum/viewtopic.php?t=91364}{\texttt{http://www.mathlinks.ro/Forum/viewtopic.php?t=91364}% }} [15] Robin Hartshorne, \textit{Algebraic Geometry}, Springer 1977. [16] Richard Stanley, \textit{Enumerative Combinatorics, Volume 1}, second edition, 15 July 2011.\newline% \texttt{\href{http://math.mit.edu/~rstan/ec/ec1/}{\texttt{http://math.mit.edu/\symbol{126}% rstan/ec/ec1/}}} [17] Manjul Bhargava, \textit{The Factorial Function and Generalizations}, The American Mathematical Monthly, Vol. 107, No. 9 (Nov., 2000), pp. 783-799. [18] Darij Grinberg, \textit{Witt\#5f: Ghost-Witt integrality for binomial rings}.\newline% \texttt{\href{http://www.cip.ifi.lmu.de/~grinberg/algebra/witt5f.pdf}{\texttt{http://www.cip.ifi.lmu.de/\symbol{126}% grinberg/algebra/witt5f.pdf}}} [19] Andreas Dress, Christian Siebeneicher, \textit{The Burnside ring of the infinite cyclic group and its relations to the necklace algebra, }$\lambda $\textit{-rings and the universal ring of Witt vectors}, Advances in Mathematics \textbf{78} (1989), pp. 1-41.\newline% \texttt{\href{http://www.sciencedirect.com/science/article/pii/0001870889900273}{\texttt{http://www.sciencedirect.com/science/article/pii/0001870889900273}% }} [20] Darij Grinberg, James Borger, \textit{MathOverflow question \#126998: Criteria for ghost-Witt vectors: looking for history and references}, 2013.\newline% \texttt{\href{http://mathoverflow.net/questions/126998}{\texttt{http://mathoverflow.net/questions/126998}% }} \end{document}