Exemplarisch zeig ich dir das mal für das erste System:
$$ p \equiv 3 \mod (4), \quad p\equiv 2 \mod (3) $$
Die Moduli (3, 4) sind teilerfremd, also existieren gemäß chinesischem Restsatz auf jeden Fall Lösungen. Diese sind eindeutig modulo kgV(3,4) = 12. Wir suchen jetzt erst einmal eine ganze Zahl x mit
$$ x \equiv \color{blue}{3}\mod (\color{green}{4}), \quad x\equiv \color{red}{2} \mod (\color{purple}{3}) $$
Der Ansatz ist folgender:
$$ x = \color{blue}{3} \cdot \color{purple}{3} \cdot a + \color{red}{2} \cdot \color{green}{4} \cdot b $$
denn wenn du das modulo 3 und 4 betrachtest:
$$ x \equiv \color{blue}{3} \cdot \color{purple}{3} \cdot a \mod (\color{green}{4}) $$ $$ x \equiv \color{red}{2} \cdot \color{green}{4} \cdot b \mod (\color{purple}{3}) $$
Um zu erreichen, dass bei der ersten Kongruenz 3 rauskommt müssen wir a so wählen, dass \( \color{purple}{3} \cdot a \equiv 1 \mod (\color{green}{4}) \), dann gilt nämlich $$ x \equiv \color{blue}{3} \cdot 1 \equiv \color{blue}{3} \mod (\color{green}{4}) $$ analog muss \( \color{green}{4} \cdot b \equiv 1 \mod (\color{purple}{3}) \) sein. a und b könntest du jetzt mit dem erweiterten euklidischen Algorithmus bestimmen oder raten. Es geht z.B. a = 3, b = 1, also ist eine Lösung $$ x = 3\cdot 3 \cdot 3 + 2 \cdot 4 \cdot 1 = 35 $$
d.h. alle \( p \) mit \( p \equiv 35 \equiv11 \mod (12) \) sind eine Lösung dieses Systems, insbesondere ist für alle Primzahlen kongruent 1 modulo 12 die 3 ein quadratischer Rest modulo \(p\).
Versuche das andere System jetzt mal selbst.
