| Chinesischer Restsatz | Anwendung [[#Definition erweiterter eukl. Algorithmus | erw. eukl. Algo]]

anchored to [[104.00_anchor_math]] proceeds from [[104.11_elementare_zahlentheorie]] also requires the knowledge for [[104.12_erweiteter_euklidischer_algorithmus]]

application or further use found in [[104.14_PolynomRinge]]

| Overview |

Mit dem Chinesischen Restsatz können wir Kongruenz-Gleichungen der folgenden Struktur lösen!

[!Important] Intuition | Betrachten wir ein Problem, bei welchem wir ein $x$ bestimmen müssen, dabei aber $n$ viele verschiedene Gleichungen der Form $x mod (p) = q$

Also etwa:

$x x x x mod (23) = mod (5) = mod (17) = mod (120) = 19280$

Um es entsprechend anwenden zu können brauchen wir noch eine Vorbetrachung:

Seien mehrere Divisoren ( also Modul-Operanden) gegeben: $m_{1}, \dots, m_{n} \in N, a \in Z$ Dann können wir die Modulo-Gruppe $M := m_{1} \cdot \dots \cdot m_{n}$ bilden -> es handelt sich also einfach um das Produkt dieser Operanden

Es folgt daraus jetzt:

[!Definition] Abhängigkeit von $a$ zu $M$ Haben wir diese Gruppe bilden können, folgt jetzt hierfür folgend: $a mod (M) mod (m_{i}) = a mod (m_{i}) \forall i$

Beweisen können wir es auch:

| Beweis (5.15) |

Teile $a$ durch $M$ mit Rest: also folgend: $$\begin{align} a = &q \cdot M + r \ r = &a \mod( M) \ q \cdot M = & m_{i} \mid M \ \implies^{\text{mit} \mod( m_{i})} & a \mod( m_{i}) = 0 + r \mod( m_{i})
\end{align}$$

Daraus können wir jetzt folgend einen Satz bilden, der das Verfahren des Chinesischen Restsatzes beschreibt -> https://en.wikipedia.org/wiki/Sunzi_Suanjing

| Satz (5.16) | Chinesischer Restsatz |

[!Defintion] Definition Chinesischer Restsatz Seien $m_{1}, \dots, m_{n} \in N$ paarweise teilerfremd Gegeben sind: -> Wir bilden dafür: $M := m_{1} \cdot \dots \cdot m_{n}$ es sind auch die Werte $a_{1}, \dots, a_{n} \in Z$ gegeben

Es existiert jetzt ein $x \leq x < M$ mit folgender Struktur: $x \equiv a_{1} mod (m_{1}) x \equiv a_{2} mod (m_{2}) \dots x \equiv a_{n} mod (m_{n})$

Wir können diese Struktur jetzt in ihrer Richtigkeit beweisen. Gleichzeitig ist es auch die Umsetzung bzw. Anwendung des Algorithmus:

| Beweis [[#Satz (5.16) Chinesischer Restsatz|5.16]] | sowie Anwendung

Für jedes $i \in {1, \dots, n}$ sind die Zahlen $m_{i}$ , sowie $M_{i} := M / m_{i}$ teilefremd –> wir entnehmen aus dem großen Produkt $M$ dann den entsprechenden Eintrag um $M_{i}$ zu bilden.

Unter Anwendung des [[#Definition erweiterter eukl. Algorithmus|EEA]] liefert dieser dann folgend: $s_{i}, t_{i} \in Z$ mit: $s_{i} \cdot M_{i} + t_{i} \cdot m_{i} = 1 (= g cd (M_{i}, m_{i}))$

Wir setzen jetzt folgend: $e_{1} := e_{i} \equiv \dots e_{i} \equiv s_{i} \cdot M_{i} (f \overset{u}{¨} r alle Eintr \overset{a}{¨} ge) 1 mod (m_{i}) 0 mod (m_{i}) \to i \neq = j$ Wir erhalten dadurch dann eine Summe, die wir folgend zusammensetzen und berechnen können: $x := x mod (m_{j}) = = = = (i = 1 \sum n a_{i} \cdot e_{i}) mod (M) das entspricht dann der L \overset{o}{¨} sung, denn: (i = 1 \sum n a_{i} \cdot e_{i}) mod (M) mod (m_{j}) (i = 1 \sum n a_{i} \cdot e_{i}) mod (m_{j}) a_{j} \cdot 1 mod (m_{j}), (dabei ist) e_{i} = 0 mit i=0 \forall j \in {1, \dots, n}$ -> Wir wissen hier, dass die resultierende Summe, die x bestimmen wird, bei den Einträgen, wo $i \neq = j$ 0 sein wird, und sonst dem Wert $a_{j}$ entspricht.

| Anwendung -> Chinesischer Restsatz |

Betrachten wir einen gesuchten Wert $X$ , welcher durch eine Menge von $n$ Gleichungen, die mit $mod ()$ abhängig sind, bestimmt werden muss.

Das heißt also, dass mit jeder Gleichung angeben wird, dass sich der Wert im Intervall von $m$ wiederholt, wobei $x mod (m) = k$ sein muss.

Wir können jetzt anschließend für jede einzelne Gleichung ein $M_{1}, M_{2}, \dots M_{n}$ bilden. Es entspricht dabei $\frac{M}{m _{i}}$ –> wobei $m_{1}$ der Wert $mod (m_{i})$ ist!

[!Important] Aufgabenstellung: Wenn wir das kleinste x finden müssen, was die Lösung bildet, dann möchten

[!Definition] Ablauf | chinesischer Restsatz | Schritte zum lösen einer w

Prüfe, ob die Zahlen teilerfremd sind

Bildet $M$

Bilde $M_{1}, M_{2}, \dots, M_{n}$

Bilde $a \cdot s + t \cdot b = 1$ aufstellen

Berechne $e_{i}$ entsprechend

Bilde jetzt gemäß der gesetzten Gleichung die Lösung

Wenn gefragt, bildet Form, sodass alle Lösungen aufgestellt werden muss

[!Warning] nicht teilerfremde Werte: Wenn zwei $m_{i}, m_{J}$ nicht teilerfremd sind, dann müssen wir sie entsprechend umstellen. Das heißt, dass wir einen der beiden Terme betrachten und schauen, wie wir diesen in der Primfaktorzerlegung bzw generell einer Zerlegung anschauen können, sodass dann: -> Die Zerteilung teilerfremd zum Rest der Werte ist!

Als Beispiel betrachten wir etwa; $x \equiv 5 mod (6) > x \equiv 1 mod (2) >$ Wir sehen hierbei, dass $2∣6$ –> 2 teilt 6 und somit nicht teilerfremd sind! Um es folgend zu lösen: -> zerteile $6 = 2 \cdot 3$ und baue die Konkruenz entsprechend auf: $x \equiv 5 mod (6) ⟹ > x \equiv 5 mod (2) ⟺ x \equiv 1 mod (2) > x \equiv 5 mod (3) ⟺ x \equiv 2 mod (3) >$

Diese Aufteilung werden wir dann auch betrachten müssen ( können hier aber den ersten Teil weglassen, weil es schon eine Gleichung gibt, die das abdeckt) Wir haben somit aufgeteilt und können den Restsatz wieder anwenden

| Beispiel Anwendung |

Ein Beispiel zur Anwendung des chinesischen Restsatz findet sich in Abgabe 08:

[[104.01_math_tutorial#Chinesischer Restsatz]]
[[104.88_assignment07]]

| Beispiel (5.17) | chinesischer Restsatz

find $o \leq x < 60$ mit $x \equiv ⎩ ⎨ ⎧ 2 mod (3) 3 mod (4) 2 mod (5)$ Wir wissen jetzt, dass: $3, 4, 5 = m_{j} bilde jetzt: M M_{1} M_{2} M_{3} ⟹ sind teilerfremd! = 3 \cdot 4 \cdot 5 = 60 = \frac{M}{m _{1}} = \frac{60}{3} = 20 = \frac{M}{m _{2}} = \frac{60}{4} = 15 = \frac{M}{m _{2}} = \frac{60}{5} = 12$ Jetzt müssen wir entsprechend den EEA 3x anwenden –> für jede aufgestellte Gleichung:

EEA: für die Gleichung in $M_{1}$ also zwischen $3, 20$ Das müssen wir auch für die anderen Bereiche, also $M_{2}$ und $M_{3}$ machen: $g cd (3, 20) = g cd (4, 15) = g cd (5, 12) = Bilde jetzt entsprechend x: x = = = 1 = 7 (s) \cdot 3 + - 1 (t) \cdot 20 1 = 4 (s) \cdot 4 + - 1 (t) \cdot 15 1 = 5 (s) \cdot 5 + - 2 (t) \cdot 12 (e_{1} \cdot a_{1} + e_{2} \cdot a_{2} + e_{3} \cdot a_{3}) mod (60 (M)) (- 20 \cdot 2 + - 15 \cdot 3 + - 24 \cdot 2) mod (60) 47$

Und damit hat man dann $x$ gefunden!

[!Important] Definition von $e_{i}$ Wir definieren hierbei $e_{i}$ mit der folgenden Struktur: Wenn wir den ggT beschreiben, dann berechnen wir $g cd (m_{i}, M_{i}) = s \cdot m_{i} + t \cdot M_{i}$ Jetzt entspricht $e_{i}$ dem Term $= t \cdot M_{i}$ –> also wir betrachten den Teil der Menge der mit $M_{i}$ korreliert !

Anwendung des Satzes:

Neben generischen Problemen, die verschiedene Modulo-Abhängigkeiten haben -> etwa Planeten-Umlaufbahnen und wann sie wieder zusammentreffen -> Wann treffen die Busse an einer Haltestelle aufeinander ( Klausuraufgabe vor zwei Jahren!)

Aber auch das schnellere / schönere Berechnen von großen Potenzen modulo:

| hohe Potenzen $mod ()$ einfach berechnen:

Betrachten wir das Beispiel: $2^{1000} mod (1155)$ ? Wir können dafür $mod (1155)$ entsprechend aufteilen ( weil es quasi $M$ ) in dieser Frage entspricht: $M = 1155 = 2^{1000} mod (3) = 2^{1000} mod (5) = 2^{1000} mod (7) = 2^{1000} mod (11) = 3 \cdot 5 \cdot 7 \cdot 11 Aufstellen: und versuchen die Struktur anders aufzuschreiben (- 1)^{1000} mod (3) = 1 mod (3) 4^{500} mod (5) (zweierPotenz!) = (- 1)^{500} mod (5) = 1 2^{3 \cdot 333 + 1} mod (7) = 8^{333} \cdot 2 mod (7) = 1 \cdot 2 mod (7) = 2 2^{5 \cdot 200} mod (11) - 3 2^{200} mod (11) = - 1^{200} mod (11) = 1$ Wir bilden jetzt folgend die Summe, um $x$ zu bestimmen: $x \equiv ⎩ ⎨ ⎧ 1 mod (3) 1 mod (5) 2 mod (7) 1 mod (11) x = 331$ Denn für diesen Wert gelten die folgenden Gleichungen

| Bemerkung (5.18) | Ring iso morphismus ( chinesischer Restsatz)

Wir können ferner auch zeigen, dass die Lösung $x$ , die wir durch den chinesischen Restsatz beschreiben können. eindeutig ist/ sein muss!.

Um das zu zeigen, können wir eine Abbildung definieren: $ψ : x Z_{M} \to Z_{M_{1}} \times Z_{M_{2}} \times \dots \times Z_{M_{n}} \mapsto (x mod (m_{1}), \dots, x mod (m_{n}))$ Wir beschreiben mit dieser dann einen Ringisomorphismus, weclhen wir in [[104.87_assignment06]] betrachten werden #TODO

[!Important] Ringisomorphismus Bedeutung: Ein Ringisomorphismus hat folgende Eigenschaften: Es handelt sich um eine strukturerhaltende bijektive Abbildung zwischen zwei Ringen

-> $ψ$ ist surjektiv, denn zu jedem n-Tupel aus $Z_{m_{1}} \times \dots \times Z_{M_{n}}$ gibt es eine Lösung $x \in Z_{M}$ -> was wir im [[#Chinesischer Restsatz Anwendung Definition erweiterter eukl. Algorithmus erw. eukl. Algo]] bereits bewiesen haben!

-> $ψ$ ist injektiv was wir durch folgende Betrachtung erkennen / erzielen können: Dabei betrachten wir folgend: $∣ Z_{M} ∣ = ∣ Z_{M} ∣= ∣ Z_{M_{1}} \times \dots \times Z Z_{M_{n}} ∣ ∣ Z_{M_{1}} \times \dots \times Z Z_{M_{n}} ∣ M = m_{1} \cdot \dots \cdot m_{n} = M$ Durch diese Betrachtung ist dann $ψ$ injektiv, weswegen auch die Lösung $x$ eindeutig sein msus.

scattered-lenity