aboutsummaryrefslogtreecommitdiffstats
path: root/buch/chapters/30-endlichekoerper
diff options
context:
space:
mode:
authorAndreas Müller <andreas.mueller@ost.ch>2021-02-04 14:39:38 +0100
committerAndreas Müller <andreas.mueller@ost.ch>2021-02-04 14:39:38 +0100
commitcbfe6fb04528537cfffb239c71e256aa3d6f75c8 (patch)
treee7701f6bcee7ea4d6edc74d024247dd7ab096e38 /buch/chapters/30-endlichekoerper
parentminor cleanup (diff)
downloadSeminarMatrizen-cbfe6fb04528537cfffb239c71e256aa3d6f75c8.tar.gz
SeminarMatrizen-cbfe6fb04528537cfffb239c71e256aa3d6f75c8.zip
new/improved binomial theorem images
Diffstat (limited to 'buch/chapters/30-endlichekoerper')
-rw-r--r--buch/chapters/30-endlichekoerper/galois.tex71
-rw-r--r--buch/chapters/30-endlichekoerper/images/Makefile5
-rw-r--r--buch/chapters/30-endlichekoerper/images/binomial5.pdfbin0 -> 26058 bytes
-rw-r--r--buch/chapters/30-endlichekoerper/images/binomial5.tex377
-rw-r--r--buch/chapters/30-endlichekoerper/images/farben.tex4
5 files changed, 453 insertions, 4 deletions
diff --git a/buch/chapters/30-endlichekoerper/galois.tex b/buch/chapters/30-endlichekoerper/galois.tex
index 63970e3..d72cc61 100644
--- a/buch/chapters/30-endlichekoerper/galois.tex
+++ b/buch/chapters/30-endlichekoerper/galois.tex
@@ -417,10 +417,33 @@ Auf den rot hinterlegten Zeilen, die zu Exponenten der Form $2^k$ gehören,
sind alle Koeffizienten ausser dem ersten und letzten durch $2$ teilbar.
\label{buch:endliche-koerper:fig:binomial2}}
\end{figure}
+\bgroup
+\input{chapters/30-endlichekoerper/images/farben.tex}
+\begin{figure}
+\centering
+\includegraphics{chapters/30-endlichekoerper/images/binomial5.pdf}
+\caption{Binomialkoeffizienten module $5$ im Pascal-Dreieck.
+Die von $0$ verschiedenen Reste werden durch Farben dargestellt:
+$1=\text{schwarz}$,
+$2=\text{\color{farbe2}rot}$,
+$3=\text{\color{farbe3}grün}$,
+$4=\text{\color{farbe4}blau}$.
+Auf den grau hinterlegten Zeilen, die zu Exponenten der Form $5^k$ gehören,
+sind alle Koeffizienten ausser dem ersten und letzten durch $5$ teilbar.
+\label{buch:endliche-koerper:fig:binomial5}}
+\end{figure}
+\egroup
Die Abbildung~\ref{buch:endliche-koerper:fig:binomial2} zeigt den
Rest bei Teilung durch $2$ der Binomialkoeffizienten.
Man kann daraus ablesen, dass $\binom{n}{m}\equiv 0\mod 2$ für $n=2^k$
und $0<m<n$.
+Abbildung~\ref{buch:endliche-koerper:fig:binomial5} zeigt das Pascal-Dreieck
+auch noch für $p=5$.
+Hier ist auch schön die Selbstähnlichkeit des Pascal-Dreiecks erkennbar.
+Ersetzt man die ``5er-Dreiecke'' durch ein volles Dreieck mit der Farbe
+des kleinen Dreiecks an seiner Spitze, entsteht wieder das ursprüngliche
+Pascal-Dreieck.
+Dabei gehen die Zeilen aus lauter Nullen ausser an den Enden ineinander über.
\begin{satz}
\label{buch:endliche-koerper:satz:binom}
@@ -443,16 +466,58 @@ im Zähler kann also nicht weggekürzt werden, so dass der Binomialkoeffizient
durch $p$ teilbar sein muss.
\end{proof}
-Die Aussage von Satz~\ref{buch:endliche-koerper:satz:binom} kann man
+\begin{satz}
+\label{buch:endliche-koerper:satz:binomk}
+Sei $p$ eine Primzahl, dann ist
+\begin{equation}
+\binom{p^k}{m} \equiv 0\mod p
+\label{buch:endliche-koerper:eqn:a+b^p^k}
+\end{equation}
+für $0<m<p^k$
+\end{satz}
+
+\begin{proof}[Beweis]
+Wir wissen aus Satz \ref{buch:endliche-koerper:satz:binom}, dass
+\begin{equation}
+(a+b)^p = a^p+b^p.
+\label{buch:endliche-koerper:eqn:a+b^p}
+\end{equation}
+Wir müssen zeigen, dass $(a+b)^{p^k}=a^{p^k}+b^{p^k}$ gilt.
+Wir verwenden vollständige Induktion,
+\eqref{buch:endliche-koerper:eqn:a+b^p} ist die Induktionsverankerung.
+Wir nehmen jetzt im Sinne der Induktionsannahme, dass
+\eqref{buch:endliche-koerper:eqn:a+b^p^k} für ein bestimmtes $k$ gilt.
+Dann ist
+\[
+(a+b)^{p^{k+1}}
+=
+(a+b)^{p^k\cdot p}
+=
+\bigl((a+b)^{p^k}\bigr)^p
+=
+(a^{p^k}+b^{p^k})^p
+=
+a^{p^k\cdot p}+b^{p^k\cdot p}
+=
+a^{p^{k+1}}
++
+b^{p^{k+1}},
+\]
+also die Behauptung für $k+1$.
+Damit ist
+\eqref{buch:endliche-koerper:eqn:a+b^p^k} für alle $k$ bewiesen.
+\end{proof}
+
+Die Aussage von Satz~\ref{buch:endliche-koerper:satz:binomk} kann man
auch im Körper $\mathbb{F}_p$ formulieren:
\begin{satz}
\label{buch:endliche-koerper:satz:binomFp}
In $\mathbb{F}_p$ gilt
\[
-\binom{p}{k}=0
+\binom{p^k}{m}=0
\]
-für $0<k<p$.
+für beliebige $k>0$ und $0<m<p$.
\end{satz}
\subsubsection{Frobenius-Automorphismus}
diff --git a/buch/chapters/30-endlichekoerper/images/Makefile b/buch/chapters/30-endlichekoerper/images/Makefile
index 466bac1..c49fe56 100644
--- a/buch/chapters/30-endlichekoerper/images/Makefile
+++ b/buch/chapters/30-endlichekoerper/images/Makefile
@@ -3,7 +3,10 @@
#
# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
#
-all: binomial2.pdf
+all: binomial2.pdf binomial5.pdf
binomial2.pdf: binomial2.tex
pdflatex binomial2.tex
+
+binomial5.pdf: binomial5.tex farben.tex
+ pdflatex binomial5.tex
diff --git a/buch/chapters/30-endlichekoerper/images/binomial5.pdf b/buch/chapters/30-endlichekoerper/images/binomial5.pdf
new file mode 100644
index 0000000..078969c
--- /dev/null
+++ b/buch/chapters/30-endlichekoerper/images/binomial5.pdf
Binary files differ
diff --git a/buch/chapters/30-endlichekoerper/images/binomial5.tex b/buch/chapters/30-endlichekoerper/images/binomial5.tex
new file mode 100644
index 0000000..bd781dd
--- /dev/null
+++ b/buch/chapters/30-endlichekoerper/images/binomial5.tex
@@ -0,0 +1,377 @@
+%
+% binomial2.tex -- Parität der Binomialkoeffizienten
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\documentclass[tikz]{standalone}
+\usepackage{amsmath}
+\usepackage{times}
+\usepackage{txfonts}
+\usepackage{pgfplots}
+\usepackage{csvsimple}
+\usetikzlibrary{arrows,intersections,math}
+\begin{document}
+\def\skala{1}
+\begin{tikzpicture}[>=latex,thick,scale=\skala]
+
+\definecolor{farbe0}{rgb}{1,1,1}
+\input{farben.tex}
+
+\def\s{0.37}
+\pgfmathparse{\s*sqrt(3)/2}
+\xdef\ys{\pgfmathresult}
+\pgfmathparse{\s/2}
+\xdef\xs{\pgfmathresult}
+
+%
+% #1 = n
+% #2 = k
+%
+\def\dreieck#1#2#3{
+ \fill[color=farbe#3] ({\xs*(-#1+2*#2)},{-\ys*#1})
+ -- ({\xs*(-#1+2*#2-1)},{-\ys*(#1+1)})
+ -- ({\xs*(-#1+2*#2+1)},{-\ys*(#1+1)}) -- cycle;
+ \node[color=gray] at ( ({\xs*(-#1+2*#2)},{-\ys*(#1+0.5)-0.03}) {$\scriptstyle #3$};
+}
+\def\zeile#1{
+ \fill[color=gray!40]
+ ({\xs*(-#1)},{-\ys*#1})
+ -- ({\xs*(-#1-1)},{-\ys*(#1+1)})
+ -- ({\xs*(#1+1)},{-\ys*(#1+1)})
+ -- ({\xs*(#1)},{-\ys*#1}) -- cycle;
+}
+
+\zeile{5}
+\zeile{25}
+
+\dreieck{0}{0}{1}
+
+\dreieck{1}{0}{1}
+\dreieck{1}{1}{1}
+
+\dreieck{2}{0}{1}
+\dreieck{2}{1}{2}
+\dreieck{2}{2}{1}
+
+\dreieck{3}{0}{1}
+\dreieck{3}{1}{3}
+\dreieck{3}{2}{3}
+\dreieck{3}{3}{1}
+
+\dreieck{4}{0}{1}
+\dreieck{4}{1}{4}
+\dreieck{4}{2}{1}
+\dreieck{4}{3}{4}
+\dreieck{4}{4}{1}
+
+\dreieck{5}{0}{1}
+\dreieck{5}{5}{1}
+
+\dreieck{6}{0}{1}
+\dreieck{6}{1}{1}
+\dreieck{6}{5}{1}
+\dreieck{6}{6}{1}
+
+\dreieck{7}{0}{1}
+\dreieck{7}{1}{2}
+\dreieck{7}{2}{1}
+\dreieck{7}{5}{1}
+\dreieck{7}{6}{2}
+\dreieck{7}{7}{1}
+
+\dreieck{8}{0}{1}
+\dreieck{8}{1}{3}
+\dreieck{8}{2}{3}
+\dreieck{8}{3}{1}
+\dreieck{8}{5}{1}
+\dreieck{8}{6}{3}
+\dreieck{8}{7}{3}
+\dreieck{8}{8}{1}
+
+\dreieck{9}{0}{1}
+\dreieck{9}{1}{4}
+\dreieck{9}{2}{1}
+\dreieck{9}{3}{4}
+\dreieck{9}{4}{1}
+\dreieck{9}{5}{1}
+\dreieck{9}{6}{4}
+\dreieck{9}{7}{1}
+\dreieck{9}{8}{4}
+\dreieck{9}{9}{1}
+
+\dreieck{10}{0}{1}
+\dreieck{10}{5}{2}
+\dreieck{10}{10}{1}
+
+\dreieck{11}{0}{1}
+\dreieck{11}{1}{1}
+\dreieck{11}{5}{2}
+\dreieck{11}{6}{2}
+\dreieck{11}{10}{1}
+\dreieck{11}{11}{1}
+
+\dreieck{12}{0}{1}
+\dreieck{12}{1}{2}
+\dreieck{12}{2}{1}
+\dreieck{12}{5}{2}
+\dreieck{12}{6}{4}
+\dreieck{12}{7}{2}
+\dreieck{12}{10}{1}
+\dreieck{12}{11}{2}
+\dreieck{12}{12}{1}
+
+\dreieck{13}{0}{1}
+\dreieck{13}{1}{3}
+\dreieck{13}{2}{3}
+\dreieck{13}{3}{1}
+\dreieck{13}{5}{2}
+\dreieck{13}{6}{1}
+\dreieck{13}{7}{1}
+\dreieck{13}{8}{2}
+\dreieck{13}{10}{1}
+\dreieck{13}{11}{3}
+\dreieck{13}{12}{3}
+\dreieck{13}{13}{1}
+
+\dreieck{14}{0}{1}
+\dreieck{14}{1}{4}
+\dreieck{14}{2}{1}
+\dreieck{14}{3}{4}
+\dreieck{14}{4}{1}
+\dreieck{14}{5}{2}
+\dreieck{14}{6}{3}
+\dreieck{14}{7}{2}
+\dreieck{14}{8}{3}
+\dreieck{14}{9}{2}
+\dreieck{14}{10}{1}
+\dreieck{14}{11}{4}
+\dreieck{14}{12}{1}
+\dreieck{14}{13}{4}
+\dreieck{14}{14}{1}
+
+\dreieck{15}{0}{1}
+\dreieck{15}{5}{3}
+\dreieck{15}{10}{3}
+\dreieck{15}{15}{1}
+
+\dreieck{16}{0}{1}
+\dreieck{16}{1}{1}
+\dreieck{16}{5}{3}
+\dreieck{16}{6}{3}
+\dreieck{16}{10}{3}
+\dreieck{16}{11}{3}
+\dreieck{16}{15}{1}
+\dreieck{16}{16}{3}
+
+\dreieck{17}{0}{1}
+\dreieck{17}{1}{2}
+\dreieck{17}{2}{1}
+\dreieck{17}{5}{3}
+\dreieck{17}{6}{1}
+\dreieck{17}{7}{3}
+\dreieck{17}{10}{3}
+\dreieck{17}{11}{1}
+\dreieck{17}{12}{3}
+\dreieck{17}{15}{1}
+\dreieck{17}{16}{2}
+\dreieck{17}{17}{1}
+
+\dreieck{18}{0}{1}
+\dreieck{18}{1}{3}
+\dreieck{18}{2}{3}
+\dreieck{18}{3}{1}
+\dreieck{18}{5}{3}
+\dreieck{18}{6}{4}
+\dreieck{18}{7}{4}
+\dreieck{18}{8}{3}
+\dreieck{18}{10}{3}
+\dreieck{18}{11}{4}
+\dreieck{18}{12}{4}
+\dreieck{18}{13}{3}
+\dreieck{18}{15}{1}
+\dreieck{18}{16}{3}
+\dreieck{18}{17}{3}
+\dreieck{18}{18}{1}
+
+\dreieck{19}{0}{1}
+\dreieck{19}{1}{4}
+\dreieck{19}{2}{1}
+\dreieck{19}{3}{4}
+\dreieck{19}{4}{1}
+\dreieck{19}{5}{3}
+\dreieck{19}{6}{2}
+\dreieck{19}{7}{3}
+\dreieck{19}{8}{2}
+\dreieck{19}{9}{3}
+\dreieck{19}{10}{3}
+\dreieck{19}{11}{2}
+\dreieck{19}{12}{3}
+\dreieck{19}{13}{2}
+\dreieck{19}{14}{3}
+\dreieck{19}{15}{1}
+\dreieck{19}{16}{4}
+\dreieck{19}{17}{1}
+\dreieck{19}{18}{4}
+\dreieck{19}{19}{1}
+
+\dreieck{20}{0}{1}
+\dreieck{20}{5}{4}
+\dreieck{20}{10}{1}
+\dreieck{20}{15}{4}
+\dreieck{20}{20}{1}
+
+\dreieck{21}{0}{1}
+\dreieck{21}{1}{1}
+\dreieck{21}{5}{4}
+\dreieck{21}{6}{4}
+\dreieck{21}{10}{1}
+\dreieck{21}{11}{1}
+\dreieck{21}{15}{4}
+\dreieck{21}{16}{4}
+\dreieck{21}{20}{1}
+\dreieck{21}{21}{1}
+
+\dreieck{22}{0}{1}
+\dreieck{22}{1}{2}
+\dreieck{22}{2}{1}
+\dreieck{22}{5}{4}
+\dreieck{22}{6}{3}
+\dreieck{22}{7}{4}
+\dreieck{22}{10}{1}
+\dreieck{22}{11}{2}
+\dreieck{22}{12}{1}
+\dreieck{22}{15}{4}
+\dreieck{22}{16}{3}
+\dreieck{22}{17}{4}
+\dreieck{22}{20}{1}
+\dreieck{22}{21}{2}
+\dreieck{22}{22}{1}
+
+\dreieck{23}{0}{1}
+\dreieck{23}{1}{3}
+\dreieck{23}{2}{3}
+\dreieck{23}{3}{1}
+\dreieck{23}{5}{4}
+\dreieck{23}{6}{2}
+\dreieck{23}{7}{2}
+\dreieck{23}{8}{4}
+\dreieck{23}{10}{1}
+\dreieck{23}{11}{3}
+\dreieck{23}{12}{3}
+\dreieck{23}{13}{1}
+\dreieck{23}{15}{4}
+\dreieck{23}{16}{2}
+\dreieck{23}{17}{2}
+\dreieck{23}{18}{4}
+\dreieck{23}{20}{1}
+\dreieck{23}{21}{3}
+\dreieck{23}{22}{3}
+\dreieck{23}{23}{1}
+
+\dreieck{24}{0}{1}
+\dreieck{24}{1}{4}
+\dreieck{24}{2}{1}
+\dreieck{24}{3}{4}
+\dreieck{24}{4}{1}
+\dreieck{24}{5}{4}
+\dreieck{24}{6}{1}
+\dreieck{24}{7}{4}
+\dreieck{24}{8}{1}
+\dreieck{24}{9}{4}
+\dreieck{24}{10}{1}
+\dreieck{24}{11}{4}
+\dreieck{24}{12}{1}
+\dreieck{24}{13}{4}
+\dreieck{24}{14}{1}
+\dreieck{24}{15}{4}
+\dreieck{24}{16}{1}
+\dreieck{24}{17}{4}
+\dreieck{24}{18}{1}
+\dreieck{24}{19}{4}
+\dreieck{24}{20}{1}
+\dreieck{24}{21}{4}
+\dreieck{24}{22}{1}
+\dreieck{24}{23}{4}
+\dreieck{24}{24}{1}
+
+\dreieck{25}{0}{1}
+\dreieck{25}{25}{1}
+
+\dreieck{26}{0}{1}
+\dreieck{26}{1}{1}
+\dreieck{26}{25}{1}
+\dreieck{26}{26}{1}
+
+\dreieck{27}{0}{1}
+\dreieck{27}{1}{2}
+\dreieck{27}{2}{1}
+\dreieck{27}{25}{1}
+\dreieck{27}{26}{2}
+\dreieck{27}{27}{1}
+
+\dreieck{28}{0}{1}
+\dreieck{28}{1}{3}
+\dreieck{28}{2}{3}
+\dreieck{28}{3}{1}
+\dreieck{28}{25}{1}
+\dreieck{28}{26}{3}
+\dreieck{28}{27}{3}
+\dreieck{28}{28}{1}
+
+\dreieck{29}{0}{1}
+\dreieck{29}{1}{4}
+\dreieck{29}{2}{1}
+\dreieck{29}{3}{4}
+\dreieck{29}{4}{1}
+\dreieck{29}{25}{1}
+\dreieck{29}{26}{4}
+\dreieck{29}{27}{1}
+\dreieck{29}{28}{4}
+\dreieck{29}{29}{1}
+
+\dreieck{30}{0}{1}
+\dreieck{30}{5}{1}
+\dreieck{30}{25}{1}
+\dreieck{30}{30}{1}
+
+\dreieck{31}{0}{1}
+\dreieck{31}{1}{1}
+\dreieck{31}{5}{1}
+\dreieck{31}{6}{1}
+\dreieck{31}{25}{1}
+\dreieck{31}{26}{1}
+\dreieck{31}{30}{1}
+\dreieck{31}{31}{1}
+
+\dreieck{32}{0}{1}
+\dreieck{32}{1}{2}
+\dreieck{32}{2}{1}
+\dreieck{32}{5}{1}
+\dreieck{32}{6}{2}
+\dreieck{32}{7}{1}
+\dreieck{32}{25}{1}
+\dreieck{32}{26}{2}
+\dreieck{32}{27}{1}
+\dreieck{32}{30}{1}
+\dreieck{32}{31}{2}
+\dreieck{32}{32}{1}
+
+\def\etikett#1#2#3{
+ \node at ({\xs*(-#1+2*#2)},{-\ys*(#1+0.5)}) {$#3$};
+}
+
+\etikett{0}{-2}{n=0}
+\etikett{5}{-2}{n=5}
+\etikett{25}{-2}{n=25}
+
+\def\exponent#1#2#3{
+ \node at ({\xs*(-#1+2*#2)},{-\ys*(#1+0.5)}) [rotate=60] {$#3$};
+}
+
+\exponent{-2}{0}{k=0}
+\exponent{3}{5}{k=5}
+\exponent{23}{25}{k=25}
+
+\end{tikzpicture}
+\end{document}
+
diff --git a/buch/chapters/30-endlichekoerper/images/farben.tex b/buch/chapters/30-endlichekoerper/images/farben.tex
new file mode 100644
index 0000000..553bb91
--- /dev/null
+++ b/buch/chapters/30-endlichekoerper/images/farben.tex
@@ -0,0 +1,4 @@
+\definecolor{farbe1}{rgb}{0,0,0}
+\definecolor{farbe2}{rgb}{1,0,0}
+\definecolor{farbe3}{rgb}{0,0.6,0}
+\definecolor{farbe4}{rgb}{0,0,1}