Konkrete Mathematik

Zahlentheorie

Grundlagen

Primzahl

Eine natürliche Zahl \(p \in \mathbb{N} \) ist genau dann eine Primzahl, wenn \(p\) genau zwei verschiedene Teiler \(1|p\) und \(p|p\) hat. Insbesondere ist 1 keine Primzahl.

Größter gemeinsamer Teiler Euklidischer Algorithmus

Der \(ggT(a,b)\) von zwei ganzen Zahlen \(a,b \in \mathbb{Z} \) ist die größte natürliche Zahl, die sowohl \(a\) als auch \(b\) teilt.

Lemma von Bézout Erweiterter euklidischer Algorithmus

Für zwei ganze Zahlen \(k,l \in \mathbb{Z}\) existieren immer zwei ganze Zahlen \(a,b \in \mathbb{Z}\) mit \(ggT(k,l) = a\cdot k + b\cdot l\).

Fundamentalsatz der Arithmetik

Jede natürliche Zahl \(n\) hat eine eindeutige Primfaktorzerlegung/Darstellung mit Primfaktoren durch \(n = \prod_{p \in \mathbb{P}} p^{n_p} \text{ mit } n_p \not= 0 \Leftrightarrow p|n\). Beispielsweise ist \(75600 = 16 \cdot 27 \cdot 25 \cdot 7 = 2^4 \cdot 3^3 \cdot 5^2 \cdot 7\).

Chinesischer Restsatz

Definition
Seien \(k,l \in \mathbb{Z}\) teilerfremd. Dann definiert folgende Zuordnung einen Ringisomorphismus: \[ \mathbb{Z}/kl\mathbb{Z} \rightarrow \mathbb{Z}/k\mathbb{Z} \times \mathbb{Z}/l\mathbb{Z}\\ x + kl\mathbb{Z} \mapsto (x + k\mathbb{Z},x + l\mathbb{Z}) \]
Definition nach Sun Zi
Seien \(m_1,\ldots,m_n \in \mathbb{Z}\) paarweise teilerfremd und sei \(m = m_1 \cdots m_n \). Für alle \(x_1,\ldots,x_n \in \mathbb{Z}\) existiert genau ein \( x \in \lbrace 1,\ldots,m-1 \rbrace \) das simultan folgende Kongruenzen erfüllt: \begin{eqnarray} x & \equiv & x_1 \mod{m_1} \\ & \vdots & \\ x & \equiv & x_n \mod{m_n} \end{eqnarray} Die Lösungsmenge ist \( x + m\mathbb{Z} \).

Primzahltest nach Fermat Kleiner Satz von Fermat \(a^p \equiv a \mod{p}\)

Algorithmus
  1. Wähle \(a \in \lbrace 1, \ldots, n-1\rbrace \) zufällig
  2. Berechne \(a^{n-1} \mod{n} \)
  3. Falls \(a^{n-1} \not\equiv 1 \mod{n} \), dann ist \(n\) keine Primzahl, ansonsten vielleicht.
Kleiner Satz von Fermat
Sei \(p\) eine Primzahl und \(a \in \mathbb{Z}\) eine ganze Zahl. Dann gilt \begin{eqnarray} a^p & \equiv & a \mod{p} \\ a^{p-1} & \equiv & 1 \mod{p-1} \text{ mit } ggT(a,p) = 1 \end{eqnarray}

Schnelle Exponentation So oft wie möglich quadrieren. Teilergebnisse modulo.

Algorithmus für \(a^b \mod{n}\)
  1. Setze \(e = 1\)
  2. Solange \(b > 0\) mache:
    1. Wenn \(b\) ungerade, setze \(e = e \cdot a \mod{n} \)
    2. Quadriere \(a = a^2 \mod{n}\)
    3. Halbiere \(b = \left\lfloor \dfrac{b}{2} \right\rfloor \)
  3. Gebe \(e\) zurück
Laufzeit
Die Laufzeit ist höchstens \(\lfloor \log_2{b} \rfloor + 1\) mit \(b\) Binärstellen. Die Anzahl der Operationen entspricht im wesentlichen höchstens \(2\) Multiplikationen pro Schleifendurchlauf. Damit lässt sich \(a^b \mod{n}\) in polynomieller Zeit berechnen.

Zahlentheorie in der Praxis

Die Zahlentheoretischen Überlegungen werden natürlich auch in der Praxis, genauer im assymetrischen Verschlüsselungsverfahren RSA, verwendet:

RSA-Verfahren Asymmetrisches Verschlüsselungsverfahren, Faktorisierungsproblem

RSA Ablauf
  1. Alice wählt zwei große Primzahlen \( 3 < p < q \)
  2. Sie berechnet \(n = pq\) und setzt \(\varphi(n)=(p-1)(q-1)\)
  3. Sie wählt einen Exponenten \(e > 1\) mit \(ggT(e,\varphi(n)) = 1\). \((n,e)\) ist der öffentliche Schlüssel.
  4. Jetzt muss sie noch das Multiplikative Inverse \(s\) zu \(e\) berechnen: \(es \equiv 1 \mod{\varphi(n)}\)
    Hierzu wird der erweiterte euklidische Algorithmus mit \(ggT(e,\varphi(n)) = 1 = e \cdot s + k \cdot \varphi(n) \) verwendet.

Zahlen

Die hier vorgestellten Zahlen kommen häufig in der Kombinatorik vor.

Binomialkoeffizient \(n\) über \(k\) \({n \choose k }\)

Definition
Der Binomialkoeffizient gibt die Menge der \(k\)-elementigen Teilmengen einer beliebigen Menge an: \[ {A \choose k } = \left\{ B \subseteq A ~ | ~\left|B\right|=k \right\} \]
Additionstheorem
\[ {n \choose k } = {n-1 \choose k-1 } + {n-1 \choose k } \]
Kombinatorische Interpretation
Der Binomialkoeffizient gibt an, wie viele \(k\)-elementige Teilmengen einer \(n\)-elementigen Menge existieren: \[ {n \choose k } = \dfrac{n!}{k! (n-k)!}\]

Recontres-Zahlen Anzahl Bijektionen mit bestimmter Zahl an Fixpunkten

Definition Fixpunktfrei
\(R_n\) ist die Anzahl der fixpunktfreien Bijektionen einer \(n\)-Elementigen Menge \(\lbrace 1,\ldots,n\rbrace\) auf sich selbst. Fixpunktfrei bedeutet, dass kein Element auf sich selbst abgebildet wird sondern immer auf ein anderes Element. \[ R_n = n! \sum_{k=0}^n \dfrac{(-1)^k}{k!} \]
Definition allgemein
\(R_{n,m}\) ist die Anzahl der Bijektionen einer \(n\)-Elementigen Menge \(\lbrace 1,\ldots,n\rbrace\) auf sich selbst mit genau \(m\) Fixpunkten. Es werden genau \(m\) Elemente auf sich selbst abgebildet. \[ R_{n,m} = \dfrac{n!}{m!} \sum_{k=0}^{n-m} \dfrac{(-1)^k}{k!} \]
Wachstum der Recontres-Zahlen

Stirling-Zahlen I \(n\) in \(k\) Zykel \( \left[ {n \atop k} \right] \)

Definition
Die Stirling-Zahlen erster Art drücken kombinatorisch die Anzahl der Permutationen über \(M = \lbrace 1,\ldots,n\rbrace\), die sich in \(k\) Zykel zerlegen lassen, aus: \[ \left[ {n \atop k} \right] := \bigl|\left\{ \pi | \pi \text{ ist Permutation von } \lbrace 1,\ldots,n \rbrace \text{ mit } k \text{ Zykeln } \right\}\bigr|\] \( \left[ {n \atop k} \right] \) wird als "\(n\) in \(k\) Zykel" ausgesprochen.
Liste für Berechnung der Stirling-Zahlen I
\(n=0\)\(n=1\)\(n=2\)\(n=3\)\(n=4\)\(n \geq 5\)
\(k=0\)\( \left[ {0 \atop 0} \right] = 1\)\( \left[ {1 \atop 0} \right] = 0\)\( \left[ {2 \atop 0} \right] = 0\)\( \left[ {3 \atop 0} \right] = 0\)\( \left[ {4 \atop 0} \right] = 0\)\( \left[ {n \atop 0} \right] = 0\)
\(k=1\)\( \left[ {0 \atop 1} \right] = 0\)\( \left[ {1 \atop 1} \right] = 1\)\( \left[ {2 \atop 1} \right] = 1\)\( \left[ {3 \atop 1} \right] = 2\)\( \left[ {4 \atop 1} \right] = 6\)\( \left[ {n \atop 1} \right] = (n-1)! \geq 24 \)
\(k=2\)\( \left[ {0 \atop 2} \right] = 0\)\( \left[ {1 \atop 2} \right] = 0\)\( \left[ {2 \atop 2} \right] = 1\)\( \left[ {3 \atop 2} \right] = 3\)\( \left[ {4 \atop 2} \right] = 11\)\( \left[ {n \atop 2} \right] = (n-2)! + (n-1) \left[ {n-1 \atop 2} \right] \geq 50 \)
\(k=3\)\( \left[ {0 \atop 3} \right] = 0\)\( \left[ {1 \atop 3} \right] = 0\)\( \left[ {2 \atop 3} \right] = 0\)\( \left[ {3 \atop 3} \right] = 1\)\( \left[ {4 \atop 3} \right] = 6\)\( \left[ {n \atop 3} \right] \geq 35 \)
\(k=4\)\( \left[ {0 \atop 4} \right] = 0\)\( \left[ {1 \atop 4} \right] = 0\)\( \left[ {2 \atop 4} \right] = 0\)\( \left[ {3 \atop 4} \right] = 0\)\( \left[ {4 \atop 4} \right] = 1\)\( \left[ {n \atop 4} \right] \geq 10 \)
\(k \geq 5\)\( \left[ {0 \atop k} \right] = 0\)\( \left[ {1 \atop k} \right] = 0\)\( \left[ {2 \atop k} \right] = 0\)\( \left[ {3 \atop k} \right] = 0\)\( \left[ {4 \atop k} \right] = 0\)\( \left[ {n \atop n} \right] = 1\)
Additionstheorem
\[ \left[ {n \atop k} \right] = \left[ {n-1 \atop k-1} \right] + (n-1) \left[ {n-1 \atop k} \right] \]
Wachstumsgesetz
\[ \left[ {n \atop k} \right] \geq (n-k)! \]

Stirling-Zahlen II \(n\) in \(k\) Klassen \(\bigl\{{n \atop k}\bigr\}\)

Definition
Die Stirling-Zahlen zweiter Art geben die Anzahl der Partitionen einer Menge mit \(n\) Elementen in \(k\) Klassen an: \[ \left\{ {n \atop k} \right\} := \bigl|\left\{ P | P \text{ ist Partition von } \lbrace 1,\ldots,n \rbrace \text{ in } k \text{ Klassen } \right\}\bigr|\] \( \left\{ {n \atop k} \right\} \) wird als "\(n\) in \(k\) Klassen" ausgesprochen.
Liste für Berechnung der Stirling-Zahlen II
\(n=0\)\(n=1\)\(n=2\)\(n=3\)\(n=4\)\(n \geq 5\)
\(k=0\)\( \left\{ {0 \atop 0} \right\} = 1\)\( \left\{ {1 \atop 0} \right\} = 0\)\( \left\{ {2 \atop 0} \right\} = 0\)\( \left\{ {3 \atop 0} \right\} = 0\)\( \left\{ {4 \atop 0} \right\} = 0\)\( \left\{ {n \atop 0} \right\} = 0\)
\(k=1\)\( \left\{ {0 \atop 1} \right\} = 0\)\( \left\{ {1 \atop 1} \right\} = 1\)\( \left\{ {2 \atop 1} \right\} = 1\)\( \left\{ {3 \atop 1} \right\} = 1\)\( \left\{ {4 \atop 1} \right\} = 1\)\( \left\{ {n \atop 1} \right\} = 1 \)
\(k=2\)\( \left\{ {0 \atop 2} \right\} = 0\)\( \left\{ {1 \atop 2} \right\} = 0\)\( \left\{ {2 \atop 2} \right\} = 1\)\( \left\{ {3 \atop 2} \right\} = 3\)\( \left\{ {4 \atop 2} \right\} = 7\)\( \left\{ {n \atop 2} \right\} = 2^{n-1}-1 \geq 15 \)
\(k=3\)\( \left\{ {0 \atop 3} \right\} = 0\)\( \left\{ {1 \atop 3} \right\} = 0\)\( \left\{ {2 \atop 3} \right\} = 0\)\( \left\{ {3 \atop 3} \right\} = 1\)\( \left\{ {4 \atop 3} \right\} = 6\)\( \left\{ {n \atop 3} \right\} \geq 25 \)
\(k=4\)\( \left\{ {0 \atop 4} \right\} = 0\)\( \left\{ {1 \atop 4} \right\} = 0\)\( \left\{ {2 \atop 4} \right\} = 0\)\( \left\{ {3 \atop 4} \right\} = 0\)\( \left\{ {4 \atop 4} \right\} = 1\)\( \left\{ {n \atop 4} \right\} \geq 10 \)
\(k \geq 5\)\( \left\{ {0 \atop k} \right\} = 0\)\( \left\{ {1 \atop k} \right\} = 0\)\( \left\{ {2 \atop k} \right\} = 0\)\( \left\{ {3 \atop k} \right\} = 0\)\( \left\{ {4 \atop k} \right\} = 0\)\( \left\{ {n \atop n} \right\} = 1\)
Additionstheorem
\[ \left\{ {n \atop k} \right\} = \left\{ {n-1 \atop k-1} \right\} + k \left\{ {n-1 \atop k} \right\} \]

Bell-Zahlen Anzahl aller Partitionen einer \(n\)-elementigen Menge

Definition
Die Bell-Zahlen geben die Anzahl aller Partitionen einer Menge mit \(n\) Elementen an: \[ B_n := \bigl|\left\{ P | P \text{ ist Partition von } \lbrace 1,\ldots,n \rbrace \right\}\bigr|\]
Wachstum der Bell-Zahlen
\(n\)\(0\)\(1\)\(2\)\(3\)\(4\)\(5\)\(6\)\(7\)\(8\)
\(B_n\)\(1\)\(1\)\(2\)\(5\)\(15\)\(52\)\(203\)\(877\)\(4140\)
Identität mit Stirling-Zahlen II
\[ B_n = \sum_k \left\{ {n \atop k} \right\} \]
Wachstumsgesetz
\[ (\dfrac{n}{2})^{\dfrac{n}{2}} \leq B_n \leq n! \text{ und } B_n \in 2^{\omega(n)} \]

Catalan-Zahlen Dyck-Wörter, Klammerausdrücke und Binärbäume

Definition
\[ C_n := \dfrac{1}{n+1} {2n \choose n } \]