diff options
Diffstat (limited to 'buch/chapters/30-endlichekoerper')
| -rw-r--r-- | buch/chapters/30-endlichekoerper/galois.tex | 71 | ||||
| -rw-r--r-- | buch/chapters/30-endlichekoerper/images/Makefile | 5 | ||||
| -rw-r--r-- | buch/chapters/30-endlichekoerper/images/binomial5.pdf | bin | 0 -> 26058 bytes | |||
| -rw-r--r-- | buch/chapters/30-endlichekoerper/images/binomial5.tex | 377 | ||||
| -rw-r--r-- | buch/chapters/30-endlichekoerper/images/farben.tex | 4 |
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 Binary files differnew file mode 100644 index 0000000..078969c --- /dev/null +++ b/buch/chapters/30-endlichekoerper/images/binomial5.pdf 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} |