TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2025W/Beispiel 76

Beweisen Sie mit Hilfe von Kongruenzen, dass zwei Quadratzahlen, deren Summe durch 3 teilbar ist, selbst durch 3 teilbar sind.

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Zu beweisen ist:

Seien $\,a,b\in \mathbb {Z} \,$ die beiden Quadratzahlen, dann ist zu zeigen, dass aus $\,3\mid {(a^{2}+b^{2})}$ folgt $3\mid {a^{2}}\,\land \,3\mid {b^{2}}$.

Hilfreiches

Wir benötigen folgende Sätze um das Beispiel lösen zu können:

$m|x\Longleftrightarrow x\equiv 0{\pmod {m}}\Longleftrightarrow x=0+q\cdot m$

$m|x\Longrightarrow x\in {\bar {0}}\in \mathbb {Z} _{m}$

Lösungsvorschlag von Anonym

Wäre hier nicht auch ein Ansatz zu beweisen das

3|a² + b² nur wahr sein kann wenn sowohl 3|a^a als auch 3|b² wahr sind? Also mittels Kontraposition:

3∤a² + 3|b^2 und vice versa verursachen 3∤a² + b²

also:

d ist ein beliebiger Rest, k ist ein Faktor

obda 3∤a => ∃k: 3*k +d = a mit d≠0

⇒ 3∤a² + 3|b² ⇒ 3∤a²+b²

= (3·k+d_a)² + (3·k+d_b)² = (9·k²+6·k·d+{1,4}) + (9·k²+6·k·d+{0,1,4})

Schlussendlich kommt hinaus d_a+d_b mod 3 da alles andre durch 3 teilbar ist.

1+0 mod 3 = 1 mod 3

4+0 mod 3 = 1 mod 3

1+1 mod 3 = 2 mod 3

4+1 mod 3 = 2 mod 3

1+4 mod 3 = 2 mod 3

4+4 mod 3 = 2 mod 3

1 oder 4 kommen durch [0 Rest = m teilt], 1² = 1, 2² Rest = 4 & der zweite Rest ist beliebig, da wir ja wegen dem Kommutativgesetz tauschen dürfen. Keine Summe der Modulo ergibt ein Mehrfaches von 3.

Bsp:

3∤4² & 3|6² ⇒ 3∤ 4² + 6²

3∤16 & 3|36 = 3∤ 16 + 36 = 3∤ 52

1 mod 3 & 0 mod 3 = 1 mod 3 qed

Hilfsmittel für Lösungsvorschläge 1, 2 und 3 von Har203

Definitionen

Im folgenden seien $a,b\in \mathbb {Z}$ und $m\in \mathbb {Z\setminus {\{0\}}}$ ganze Zahlen. Zwei Zahlen $a$ und $b$ heißen kongruent modulo $m$, wenn $m$ die Differenz $(a-b)$ teilt.

$a\equiv b{\bmod {m}}\iff m\mid {(a-b)}\iff \exists \;k\in \mathbb {Z} :a=k\cdot {m}+b$

Rechenregeln

Im Folgenden seien $a,b\in \mathbb {Z} ,\;m\in \mathbb {Z\setminus {\{0\}}}$ ganze Zahlen und $n\in \mathbb {N_{0}}$ eine natürliche Zahl.

Dann gelten folgende Rechenregeln:

${\begin{aligned}a\equiv {0{\bmod {m}}}&\iff m\mid {a}&{\text{(Teilbarkeit)}}\quad (1)&\\a\equiv {a{\bmod {m}}}&&{\text{(Reflexivität)}}\quad (2)&\\a\equiv {b{\bmod {m}}}&\iff b\equiv {a{\bmod {m}}}&{\text{(Symmetrie)}}\quad (3)&\\a\equiv {b{\bmod {m}}}&\implies a^{n}\equiv {b^{n}{\bmod {m}}}&{\text{(Potenzen)}}\quad (4)&\end{aligned}}$

Verwendete Vorgaben, Annahmen, Zusätze und Beweise

In den drei Lösungen 1, 2 und 3 werde ich zwei beliebige ganze Zahlen $a,b\in \mathbb {Z}$ mit Rest einer ganzzahligen Division durch die Zahl Drei folgend darstellen:

Es seien $a=\mathbf {3\cdot } k_{a}+r_{a}$ und $b=\mathbf {3\cdot } k_{b}+r_{b}$ zwei ganze Zahlen aus $\mathbb {Z}$ mit $k_{a},k_{b}\in \mathbb {Z}$ und $r_{a},r_{b}\in \{\mathbf {0} ,\mathbf {1} ,\mathbf {2} \}$ als Vertreter der Restklassen $\{\mathbf {\bar {0}} ,\mathbf {\bar {1}} ,\mathbf {{\bar {2}}\}} \in \mathbb {Z_{3}}$.$\qquad (5)$

${\begin{aligned}a^{2}&=(3\cdot k_{a}+r_{a})^{2}=\mathbf {3\cdot } (3\cdot k_{a}^{2}+2\cdot k_{a}\cdot r_{a})+(\,r_{a}^{2}\,)&(\,a^{2}\,)\quad (6)&\\b^{2}&=(3\cdot k_{b}+r_{b}\,)^{2}=\mathbf {3\cdot } (3\cdot k_{b}^{2}+2\cdot k_{b}\cdot r_{b})+(\,r_{b}^{2}\,)&(\,b^{2}\,)\quad (7)&\\[1ex]a^{2}+b^{2}&=(3\cdot k_{a}+r_{a})^{2}+(3\cdot k_{b}+r_{b}\,)^{2}=\mathbf {3\cdot } (3\cdot k_{a}^{2}+3\cdot k_{b}^{2}+2\cdot k_{a}\cdot r_{a}+2\cdot k_{b}\cdot r_{b})+(r_{a}^{2}+r_{b}^{2})\,\mathbf {\implies a^{2}+b^{2}\,\equiv \,r_{a}^{2}+r_{b}^{2}\,{\bmod {3}}} &(\,a^{2}+b^{2}\,)\quad (8)&\end{aligned}}$

Da ich in den Lösungen 2 und 3 nicht nur die Implikation $3\mid {(a^{2}+b^{2})}\Rightarrow 3\mid {a^{2}}\,\land \,3\mid {b^{2}}$, sondern insgesamt $\,3\mid {(a^{2}+b^{2})}\iff 3\mid {a^{2}}\,\land \,3\mid {b^{2}}\iff 3\mid {a}\,\land \,3\mid {b}\,$ zeigen werde, benötige ich noch den Beweis für folgende Aussage:

Sei $\,p\in \mathbb {N} \,$ eine beliebige Primzahl und $a\in \mathbb {Z}$, dann gilt:

${\begin{aligned}&p\mid {a^{2}}\iff p\mid {a}.\qquad \qquad \qquad \qquad \qquad \qquad {\text{(Primzahlteiler)}}\quad (9)\end{aligned}}$

Beweis:

Die Aussage folgt aus dem Fundamentalsatz der Arithmetik, der Eindeutigkeit der Primfaktorzerlegung (bis auf die Reihenfolge der Faktoren):

Wenn $p$ eine Primzahl ist und $p\mid {a^{2}}$, dann muss $p$ in der Primfaktorzerlegung von $a^{2}$ vorkommen und damit auch in jener von $a$. Daraus folgt, dass $p\mid {a}$.

Aus $\;p\mid {a}\implies \exists \;k_{p}\in \mathbb {Z}$ mit $\,a=p\cdot k_{p}$

$a^{2}=(p\cdot k_{p})^{2}=\mathbf {p^{2}\cdot } (\,k_{p}^{2}\,)=\mathbf {p\cdot } (\,p\cdot k_{p}^{2}\,)\implies p^{2}\mid {a^{2}}\,\land \,p\mid {a^{2}}$. $\qquad \blacksquare$

Beispiele

Seien $\,a^{2},b^{2}\,$ die beiden Quadratzahlen mit $k_{a},k_{b}\in \mathbb {Z}$ und $r_{a},r_{b}\in \{\mathbb {0} ,\mathbb {1} ,\mathbb {2} \}$ als Vertreter der Restklassen $\{\mathbb {\bar {0}} ,\mathbb {\bar {1}} ,\mathbb {{\bar {2}}\}} \in \mathbb {Z_{3}}$

${\begin{aligned}&a=\mathbf {3\cdot } k_{a}+r_{a}\\&b=\mathbf {3\cdot } k_{b}+r_{b}\\[1ex]&{\text{RF }}\mathbb {\bar {r_{a}^{2}}} \,\ldots {\text{ die Restklasse von }}\,r_{a}^{2}\,{\text{ bezüglich }}\,\mathbb {Z_{3}} \\&3\mid {r_{b}}:{\text{ W für Wahr}}\implies 3\mid {r_{b}}\,\land \,{\text{ F für Falsch}}\implies 3\nmid {r_{b}}\end{aligned}}$

$\,\mathbf {a} \,$	$\,\mathbf {b} \,$	$\,a^{2}\,$	$\,b^{2}\,$	$\,r_{a}\,$	$\,r_{a}^{2}\,$	RK $\,\mathbf {\bar {r_{a}}} \,$	RK $\,\mathbf {\bar {r_{a}^{2}}} \,$	$\,r_{b}\,$	$\,r_{b}^{2}\,$	RK $\,\mathbf {\bar {r_{b}}} \,$	RK $\,\mathbf {\bar {r_{b}^{2}}} \,$	$\,a^{2}+b^{2}\,$	$\,r_{a}^{2}+r_{b}^{2}\,$	RK $\,\mathbf {\bar {r_{a}^{2}+r_{b}^{2}}} \,$	$\,3|a=3|a^{2}=3|r_{a}=3|r_{a}^{2}\,$	$\,3|b=3|r_{b}=3|b^{2}=3|r_{b}^{2}\,$
$\,\mathbf {0} \,$	$\,\mathbf {0} \,$	$\,0\,$	$\,0\,$	$\,0\,$	$\,0\,$	$\,\mathbf {\bar {0}} \,$	$\,\mathbf {\bar {0}} \,$	$\,0\,$	$\,0\,$	$\,\mathbf {\bar {0}} \,$	$\,\mathbf {\bar {0}} \,$	$\,0\,$	$\,0\,$	$\,\mathbf {\bar {0}} \,$	$\,W\,$	$\,W\,$
$\,\mathbf {1} \,$	$\,\mathbf {0} \,$	$\,1\,$	$\,0\,$	$\,1\,$	$\,1\,$	$\,\mathbf {\bar {1}} \,$	$\,\mathbf {\bar {1}} \,$	$\,0\,$	$\,0\,$	$\,\mathbf {\bar {0}} \,$	$\,\mathbf {\bar {0}} \,$	$\,1\,$	$\,1\,$	$\,\mathbf {\bar {1}} \,$	$\,F\,$	$\,W\,$
$\,\mathbf {2} \,$	$\,\mathbf {0} \,$	$\,4\,$	$\,0\,$	$\,2\,$	$\,4\,$	$\,\mathbf {\bar {2}} \,$	$\,\mathbf {\bar {1}} \,$	$\,0\,$	$\,0\,$	$\,\mathbf {\bar {0}} \,$	$\,\mathbf {\bar {0}} \,$	$\,4\,$	$\,4\,$	$\,\mathbf {\bar {1}} \,$	$\,F\,$	$\,W\,$
$\,\mathbf {3} \,$	$\,\mathbf {0} \,$	$\,9\,$	$\,0\,$	$\,0\,$	$\,0\,$	$\,\mathbf {\bar {0}} \,$	$\,\mathbf {\bar {0}} \,$	$\,0\,$	$\,0\,$	$\,\mathbf {\bar {0}} \,$	$\,\mathbf {\bar {0}} \,$	$\,9\,$	$\,0\,$	$\,\mathbf {\bar {0}} \,$	$\,W\,$	$\,W\,$
$\,\mathbf {1} \,$	$\,\mathbf {1} \,$	$\,1\,$	$\,1\,$	$\,1\,$	$\,1\,$	$\,\mathbf {\bar {1}} \,$	$\,\mathbf {\bar {1}} \,$	$\,1\,$	$\,1\,$	$\,\mathbf {\bar {1}} \,$	$\,\mathbf {\bar {1}} \,$	$\,2\,$	$\,2\,$	$\,\mathbf {\bar {2}} \,$	$\,F\,$	$\,F\,$
$\,\mathbf {2} \,$	$\,\mathbf {1} \,$	$\,4\,$	$\,1\,$	$\,2\,$	$\,4\,$	$\,\mathbf {\bar {2}} \,$	$\,\mathbf {\bar {1}} \,$	$\,1\,$	$\,1\,$	$\,\mathbf {\bar {1}} \,$	$\,\mathbf {\bar {1}} \,$	$\,5\,$	$\,5\,$	$\,\mathbf {\bar {2}} \,$	$\,F\,$	$\,F\,$
$\,\mathbf {3} \,$	$\,\mathbf {1} \,$	$\,9\,$	$\,1\,$	$\,0\,$	$\,0\,$	$\,\mathbf {\bar {0}} \,$	$\,\mathbf {\bar {0}} \,$	$\,1\,$	$\,1\,$	$\,\mathbf {\bar {1}} \,$	$\,\mathbf {\bar {1}} \,$	$\,10\,$	$\,1\,$	$\,\mathbf {\bar {1}} \,$	$\,W\,$	$\,F\,$
$\,\mathbf {1} \,$	$\,\mathbf {2} \,$	$\,1\,$	$\,4\,$	$\,1\,$	$\,1\,$	$\,\mathbf {\bar {1}} \,$	$\,\mathbf {\bar {1}} \,$	$\,2\,$	$\,4\,$	$\,\mathbf {\bar {2}} \,$	$\,\mathbf {\bar {1}} \,$	$\,5\,$	$\,5\,$	$\,\mathbf {\bar {2}} \,$	$\,F\,$	$\,F\,$
$\,\mathbf {2} \,$	$\,\mathbf {2} \,$	$\,4\,$	$\,4\,$	$\,2\,$	$\,4\,$	$\,\mathbf {\bar {2}} \,$	$\,\mathbf {\bar {1}} \,$	$\,2\,$	$\,4\,$	$\,\mathbf {\bar {2}} \,$	$\,\mathbf {\bar {1}} \,$	$\,8\,$	$\,8\,$	$\,\mathbf {\bar {2}} \,$	$\,F\,$	$\,F\,$
$\,\mathbf {3} \,$	$\,\mathbf {2} \,$	$\,9\,$	$\,4\,$	$\,0\,$	$\,0\,$	$\,\mathbf {\bar {0}} \,$	$\,\mathbf {\bar {0}} \,$	$\,2\,$	$\,4\,$	$\,\mathbf {\bar {2}} \,$	$\,\mathbf {\bar {1}} \,$	$\,13\,$	$\,4\,$	$\,\mathbf {\bar {1}} \,$	$\,W\,$	$\,F\,$
$\,\mathbf {1} \,$	$\,\mathbf {3} \,$	$\,1\,$	$\,9\,$	$\,1\,$	$\,1\,$	$\,\mathbf {\bar {1}} \,$	$\,\mathbf {\bar {1}} \,$	$\,0\,$	$\,0\,$	$\,\mathbf {\bar {0}} \,$	$\,\mathbf {\bar {0}} \,$	$\,10\,$	$\,1\,$	$\,\mathbf {\bar {1}} \,$	$\,F\,$	$\,W\,$
$\,\mathbf {2} \,$	$\,\mathbf {3} \,$	$\,4\,$	$\,9\,$	$\,2\,$	$\,4\,$	$\,\mathbf {\bar {2}} \,$	$\,\mathbf {\bar {1}} \,$	$\,0\,$	$\,0\,$	$\,\mathbf {\bar {0}} \,$	$\,\mathbf {\bar {0}} \,$	$\,13\,$	$\,4\,$	$\,\mathbf {\bar {1}} \,$	$\,F\,$	$\,W\,$
$\,\mathbf {3} \,$	$\,\mathbf {3} \,$	$\,9\,$	$\,9\,$	$\,0\,$	$\,0\,$	$\,\mathbf {\bar {0}} \,$	$\,\mathbf {\bar {0}} \,$	$\,0\,$	$\,0\,$	$\,\mathbf {\bar {0}} \,$	$\,\mathbf {\bar {0}} \,$	$\,18\,$	$\,0\,$	$\,\mathbf {\bar {0}} \,$	$\,W\,$	$\,W\,$
$\,\mathbf {4} \,$	$\,\mathbf {12} \,$	$\,16\,$	$\,144\,$	$\,1\,$	$\,1\,$	$\,\mathbf {\bar {1}} \,$	$\,\mathbf {\bar {1}} \,$	$\,0\,$	$\,0\,$	$\,\mathbf {\bar {0}} \,$	$\,\mathbf {\bar {0}} \,$	$\,160\,$	$\,1\,$	$\,\mathbf {\bar {1}} \,$	$\,F\,$	$\,W\,$
$\,\mathbf {6} \,$	$\,\mathbf {12} \,$	$\,36\,$	$\,144\,$	$\,0\,$	$\,0\,$	$\,\mathbf {\bar {0}} \,$	$\,\mathbf {\bar {0}} \,$	$\,0\,$	$\,0\,$	$\,\mathbf {\bar {0}} \,$	$\,\mathbf {\bar {0}} \,$	$\,180\,$	$\,0\,$	$\,\mathbf {\bar {0}} \,$	$\,W\,$	$\,W\,$
$\,\mathbf {8} \,$	$\,\mathbf {20} \,$	$\,64\,$	$\,400\,$	$\,2\,$	$\,4\,$	$\,\mathbf {\bar {2}} \,$	$\,\mathbf {\bar {1}} \,$	$\,2\,$	$\,4\,$	$\,\mathbf {\bar {2}} \,$	$\,\mathbf {\bar {1}} \,$	$\,464\,$	$\,8\,$	$\,\mathbf {\bar {2}} \,$	$\,F\,$	$\,F\,$
$\,\mathbf {9} \,$	$\,\mathbf {14} \,$	$\,81\,$	$\,196\,$	$\,0\,$	$\,0\,$	$\,\mathbf {\bar {0}} \,$	$\,\mathbf {\bar {0}} \,$	$\,2\,$	$\,4\,$	$\,\mathbf {\bar {2}} \,$	$\,\mathbf {\bar {1}} \,$	$\,277\,$	$\,4\,$	$\,\mathbf {\bar {1}} \,$	$\,W\,$	$\,F\,$
$\,\mathbf {9} \,$	$\,\mathbf {15} \,$	$\,81\,$	$\,225\,$	$\,0\,$	$\,0\,$	$\,\mathbf {\bar {0}} \,$	$\,\mathbf {\bar {0}} \,$	$\,0\,$	$\,0\,$	$\,\mathbf {\bar {0}} \,$	$\,\mathbf {\bar {0}} \,$	$\,306\,$	$\,0\,$	$\,\mathbf {\bar {0}} \,$	$\,W\,$	$\,W\,$

Lösungsvorschlage 1 (Die kurze Variante) von Har203

Die kurze Lösungsvariante mit Kongruenzen beinhaltet nur den Beweis $\,3\mid {(a^{2}+b^{2})}\Rightarrow 3\mid {a^{2}}\,\land \,3\mid {b^{2}}$

Nach (8) gilt:

$a^{2}+b^{2}=\mathbf {3\cdot } (3\cdot k_{a}^{2}+3\cdot k_{b}^{2}+2\cdot k_{a}\cdot r_{a}+2\cdot k_{b}\cdot r_{b})+(r_{a}^{2}+r_{b}^{2})\,\mathbf {\implies a^{2}+b^{2}\,\equiv \,r_{a}^{2}+r_{b}^{2}\,{\bmod {3}}}$ 

$\implies 3\mid {(a^{2}+b^{2})}\iff \mathbf {r_{a}^{2}+r_{b}^{2}\,\equiv \,0\,{\bmod {3}}}$

Wir benötigen die Kongruenz, da zum Beispiel im folgenden Fall, zwar keine Lösung, jedoch die Addition der Quadrate größer als drei wird:

$r_{a}=2$ und $r_{b}=1\implies r_{a}^{2}=4$ und $r_{b}^{2}=1\implies r_{a}^{2}+r_{b}^{2}=5\,\equiv \,2\,{\bmod {3}}\implies r_{a}^{2}+r_{b}^{2}\in$ Restklasse $\mathbf {\bar {2}}$.

Für $\,r_{a}^{2}+r_{b}^{2}\,\equiv \,0\,{\bmod {3}}\,$ gibt es für Lösungen drei Möglichkeiten ($\,r_{a},r_{b}\,\in \{\mathbb {0} ,\mathbb {1} ,\mathbb {2} \}$):

${\begin{alignedat}{1}r_{a}^{2}+r_{b}^{2}=\left\lbrace \;{\begin{aligned}\;0:\;&\implies r_{a}^{2}=0\implies r_{b}^{2}=0&\mathbf {{\text{(Lösung }}\;\checkmark {\text{)}}} \\\;3:\;&\implies r_{a}^{2}=1\implies r_{b}^{2}=2\;{\text{(Widerspruch }}\;\times {\text{)}}\,\lor \,r_{b}^{2}=1\implies r_{a}^{2}=2\;{\text{(Widerspruch }}\;\times {\text{)}}&\;\mathbf {{\text{(Widerspruch }}\;\times {\text{)}}} \\\;6:\;&\implies r_{a}^{2}=4\implies r_{b}^{2}=2\;{\text{(Widerspruch }}\;\times {\text{)}}\,\lor \,r_{b}^{2}=4\implies r_{a}^{2}=2\;{\text{(Widerspruch }}\;\times {\text{)}}&\;\mathbf {{\text{(Widerspruch }}\;\times {\text{)}}} \end{aligned}}\right.\end{alignedat}}$ 

Daraus folgt, dass es nur dann und genau dann eine Lösung gibt, wenn $\,r_{a}^{2}=0\,\land \,r_{b}^{2}=0\,{\text{:}}\,\implies$

$3\mid {(a^{2}+b^{2})}\iff r_{a}^{2}=r_{a}=0\,\land \,r_{b}^{2}=r_{b}=0\iff 3\mid {a^{2}}\,\land \,3\mid {b^{2}}$. $\qquad \blacksquare$

Lösungsvorschlage 2 (Der direkte Weg) von Har203

Ich werde den direkten Weg gehen und verwende $\;a,b\;$, wie oben in $(5)$ angegeben.

Zu beweisen ist, dass $\,3\mid {(a^{2}+b^{2})}\Rightarrow 3\mid {a^{2}}\,\land \,3\mid {b^{2}}$. Ich werde zusätzlich zeigen, dass $\,3\mid {(a^{2}+b^{2})}\iff 3\mid {a^{2}}\;\land \;3\mid {b^{2}}\iff 3\mid {a}\;\land \;3\mid {b}$

Beweis:

Aus (8) folgt:

${\begin{aligned}3\mid {(a^{2}+b^{2})}&\iff a^{2}+b^{2}=\mathbf {3\cdot } k_{1}+(\,r_{a}^{2}+r_{b}^{2}\,)\;{\text{ mit }}\,(\,r_{a}^{2}+r_{b}^{2}\,)\equiv {0}{\bmod {3}}\;,\,k_{1}=3\cdot k_{a}^{2}+3\cdot k_{b}^{2}+2\cdot k_{a}\cdot r_{a}+2\cdot k_{b}\cdot r_{b},\;k_{1}\in \mathbb {Z} \\[1ex]r_{a}^{2}+r_{b}^{2}\equiv {0}\,{\bmod {3}}&\iff r_{a}=0\;\land \;r_{b}=0\,{\text{, sprich }}\iff 3\mid {a^{2}}\;\land \;3\mid {b^{2}}\iff {\text{(aus }}(9){\text{ mit Primzahl }}p=3{\text{) }}\;3\mid {a}\;\land \;3\mid {b}.\end{aligned}}$

Die Überprüfung führen wir am einfachsten über eine Tabelle durch:

$\;r_{a}\;$	$\;r_{b}\;$	$\rightarrow$	$\;r_{a}^{2}\;$	Restklasse $r_{a}^{2}{\bmod {3}}$	$\;r_{b}^{2}\;$	Restklasse $r_{b}^{2}{\bmod {3}}$	$\;r_{a}^{2}+r_{b}^{2}\;$	Restklasse $(r_{a}^{2}+r_{b}^{2}){\bmod {3}}$
$0$	$0$	$\rightarrow$	$0$	$\mathbf {\bar {0}}$	$0$	$\mathbf {\bar {0}}$	$0$	$\mathbf {\bar {0}}$
$0$	$1$	$\rightarrow$	$0$	$\mathbf {\bar {0}}$	$1$	$\mathbf {\bar {1}}$	$1$	$\mathbf {\bar {1}}$
$0$	$2$	$\rightarrow$	$0$	$\mathbf {\bar {0}}$	$4$	$\mathbf {\bar {1}}$	$4$	$\mathbf {\bar {1}}$
$1$	$0$	$\rightarrow$	$1$	$\mathbf {\bar {1}}$	$0$	$\mathbf {\bar {0}}$	$1$	$\mathbf {\bar {1}}$
$1$	$1$	$\rightarrow$	$1$	$\mathbf {\bar {1}}$	$1$	$\mathbf {\bar {1}}$	$2$	$\mathbf {\bar {2}}$
$1$	$2$	$\rightarrow$	$1$	$\mathbf {\bar {1}}$	$4$	$\mathbf {\bar {1}}$	$5$	$\mathbf {\bar {2}}$
$2$	$0$	$\rightarrow$	$4$	$\mathbf {\bar {1}}$	$0$	$\mathbf {\bar {0}}$	$4$	$\mathbf {\bar {1}}$
$2$	$1$	$\rightarrow$	$4$	$\mathbf {\bar {1}}$	$1$	$\mathbf {\bar {1}}$	$5$	$\mathbf {\bar {2}}$
$2$	$2$	$\rightarrow$	$4$	$\mathbf {\bar {1}}$	$4$	$\mathbf {\bar {1}}$	$8$	$\mathbf {\bar {2}}$

$\Longrightarrow \,$ Die Restklasse $\,\mathbf {\bar {0}} \,$ für $\,(r_{a}^{2}+r_{b}^{2}){\bmod {3}}\,$ ergibt sich $\iff r_{a}=0\;\mathbf {\land } \;r_{b}=0\iff 3\mid {(a^{2}+b^{2})}\iff 3\mid {a^{2}}\;\mathbf {\land } \;3\mid {b^{2}}\iff {\text{(aus }}(9){\text{ mit Primzahl }}p=3{\text{) }}\;3\mid {a}\;\mathbf {\land } \;3\mid {b}$. $\qquad \blacksquare$

Lösungsvorschlage 3 (Die Kontraposition) von Har203

Ein anderer Lösungsweg ist über die Kontraposition, also den "Umkehrschluss". Ich verwende wieder $\;a,b\;$, wie oben in $(5)$ angegeben. Ich werde folgende vier Fälle betrachten:

${\begin{alignedat}{2}&\left.{\begin{aligned}&{\text{Fall 1:}}&3\nmid {a^{2}}\,\land \,3\nmid {b^{2}}\\&{\text{Fall 2a:}}&3\mid {a^{2}}\,\land \,3\nmid {b^{2}}\\&{\text{Fall 2b:}}&3\nmid {a^{2}}\,\land \,3\mid {b^{2}}\end{aligned}}\,\right\rbrace &\,&\implies &3\nmid {(a^{2}+b^{2})}\\[1ex]&\left.{\begin{aligned}&{\text{Fall 3:}}\;\;&3\mid {a^{2}}\,\land \,3\mid {b^{2}}\end{aligned}}\,\right.&\,&\implies &3\mid {(a^{2}+b^{2})}\end{alignedat}}$

Zu beweisen sind vorab die drei ersten oben angeführten Fälle: Fall 1, Fall 2a und Fall 2b:

Beweis:

$\mathbf {\text{Fall 1: }} \;3\nmid {a^{2}}\;\land \;3\nmid {b^{2}}\implies 3\nmid {(a^{2}+b^{2})}$

Aus $(6),(7)$ folgt: $3\nmid {a^{2}}\implies r_{a}^{2}\neq {0}\;\land \;3\nmid {b^{2}}\implies r_{b}^{2}\neq {0}$.

Die Überprüfung $\,3\nmid {a^{2}}\;\land \;3\nmid {b^{2}}\implies 3\nmid {(a^{2}+b^{2})}\,$ führen wir über eine Tabelle durch (Fall 1):

Fall	$r_{a}$	$r_{b}$	$\rightarrow$	$r_{a}^{2}$	Restklasse $r_{a}^{2}{\bmod {3}}$	$r_{b}^{2}$	Restklasse $r_{b}^{2}{\bmod {3}}$	$r_{a}^{2}+r_{b}^{2}$	Restklasse $(r_{a}^{2}+r_{b}^{2}){\bmod {3}}$
3	$0$	$0$	$\rightarrow$	$0$	$0$	$0$	$0$	$0$	${\bar {0}}$
2a	$0$	$1$	$\rightarrow$	$0$	$0$	$1$	$1$	$1$	${\bar {1}}$
2a	$0$	$2$	$\rightarrow$	$0$	$0$	$4$	$1$	$4$	${\bar {1}}$
2b	$1$	$0$	$\rightarrow$	$1$	$1$	$0$	$0$	$1$	${\bar {1}}$
1	$1$	$1$	$\rightarrow$	$1$	$1$	$1$	$1$	$2$	${\bar {2}}$
1	$1$	$2$	$\rightarrow$	$1$	$1$	$4$	$1$	$5$	${\bar {2}}$
2b	$2$	$0$	$\rightarrow$	$4$	$1$	$0$	$0$	$4$	${\bar {1}}$
1	$2$	$1$	$\rightarrow$	$4$	$1$	$1$	$1$	$5$	${\bar {2}}$
1	$2$	$2$	$\rightarrow$	$4$	$1$	$4$	$1$	$8$	${\bar {2}}$

$\Longrightarrow \,$ Fall 1: Die Restklasse ${\bar {0}}$ wird nicht erreicht: $(r_{a}^{2}+r_{b}^{2})\equiv {2}{\bmod {3}}\implies (r_{a}^{2}+r_{b}^{2})\not \equiv {0}{\bmod {3}}\implies 3\nmid {(a^{2}+b^{2})}$.

$\mathbf {\text{Fall 2a: }} \;3\mid {a^{2}}\;\land \;3\nmid {b^{2}}\implies 3\nmid {(a^{2}+b^{2})}$

Aus $(6),(7)$ folgt: $3\mid {a^{2}}\implies r_{a}^{2}=0\;\land \;3\nmid {b^{2}}\implies r_{b}^{2}\neq {0}$.

$\mathbf {\text{Fall 2b: }} \;3\nmid {a^{2}}\;\land \;3\mid {b^{2}}\implies 3\nmid {(a^{2}+b^{2})}$

Aus $(6),(7)$ folgt: $3\nmid {a^{2}}\implies r_{a}^{2}\neq {0}\;\land \;3\mid {b^{2}}\implies r_{b}^{2}=0$.

Die Überprüfungen $\,3\mid {a^{2}}\;\land \;3\nmid {b^{2}}\;$ (Fall 2a) bzw. $3\nmid {a^{2}}\;\land \;3\mid {b^{2}}\;$ (Fall 2b) $\implies 3\nmid {(a^{2}+b^{2})}\,$ führen wir wieder über die oben angeführte Tabelle #Tabelle-Restklassen durch.

$\Longrightarrow \,$ Fall 2a und Fall 2b: Die Restklasse ${\bar {0}}$ wird nicht erreicht: $\,(r_{a}^{2}+r_{b}^{2})\equiv {1}{\bmod {3}}\implies (r_{a}^{2}+r_{b}^{2})\not \equiv {0}{\bmod {3}}\implies 3\nmid {(a^{2}+b^{2})}$.

$\mathbf {\text{Fall 3: }} \;3\mid {a^{2}}\;\land \;3\mid {b^{2}}\implies 3\mid {(a^{2}+b^{2})}$

Aus $3\mid {a^{2}}\implies r_{a}=0\;\land \;3\mid {b^{2}}\implies r_{b}=0$.

Die Überprüfung $\,3\mid {a^{2}}\;\land \;3\mid {b^{2}}\implies 3\mid {(a^{2}+b^{2})}\;$ führen wir wieder über die Tabelle #Tabelle-Restklassen durch (Fall 3).

$\Longrightarrow \,$ Fall 3: Die Restklasse ${\bar {0}}$ wird erreicht: $(r_{a}^{2}+r_{b}^{2})\equiv {0}{\bmod {3}}\implies 3\mid {(a^{2}+b^{2})}$.$\quad$

Anmerkung zu Fall 3:

Diesen Fall müssten wir eigentlich nicht separat betrachten, da in der Angabe nicht nach dem Umkehrschluss und nicht nach der Existenz von Lösungen gefragt wird, sondern nach der Implikation $3\mid {(a^{2}+b^{2})}\implies 3\mid {a^{2}}\;\land \;3\mid {b^{2}}$. Diese Implikation folgt bereits aus der Kontraposition der Fälle 1, 2a und 2b.

Für die beidseitige Folgerung $\mathbf {3\mid {(a^{2}+b^{2})}\iff 3\mid {a^{2}}\;\land \;3\mid {b^{2}}\iff } {\text{(aus }}(9){\text{ mit Primzahl }}p=3{\text{) }}\;\mathbf {3\mid {a}\;\land \;3\mid {b}}$ wird der Fall 3 jedoch benötigt. $\qquad \blacksquare$