MNG_Kapitel_1_Uebung (AI)

Bestimmen Sie den größten gemeinsamen Teiler von $a = 486$ und $b = 243$ mit dem euklidischen Algorithmus.

Berechnen Sie den größten gemeinsamen Teiler von $a = 1365$ und $b = 850$ mit Hilfe des Euklidischen Algorithmus.

Bestimmen Sie mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von 1071 und 462.

Erklären Sie, warum der euklidische Algorithmus zur Bestimmung des ggT stets abbricht und was dies mit der Rationalität der beteiligten Zahlen zu tun hat. Wenn der ggT von zwei Zahlen a und b gleich 1 ist, was kann man dann über die Rationalität des Bruches $\frac{a}{b}$ aussagen?

Nehmen Sie an, $\sqrt{2}$ sei rational. Dann kann $\sqrt{2}$ als Bruch $\frac{m}{n}$ dargestellt werden, wobei $m$ und $n$ ganze Zahlen sind und der Bruch vollständig gekürzt ist (d.h., $m$ und $n$ sind teilerfremd). Stellen Sie die Gleichung auf, die aus dieser Annahme resultiert.

Leiten Sie aus der Gleichung aus Teilaufgabe 1a her, dass $m^2$ eine gerade Zahl ist. Was folgt daraus für $m$?

Da $m$ gerade ist, kann es als $m = 2k$ geschrieben werden, wobei $k$ eine ganze Zahl ist. Setzen Sie diesen Ausdruck für $m$ in die Gleichung $2n^2 = m^2$ ein und vereinfachen Sie die Gleichung.

Was können Sie aus der vereinfachten Gleichung in Teilaufgabe 1c über $n$ schließen? Wie führt dies zu einem Widerspruch zur anfänglichen Annahme, und welche Schlussfolgerung kann daraus gezogen werden?

Zeigen Sie, dass für jede Primzahl $p > 3$ gilt: $p^2 \equiv 1 \pmod{24}$.

Bestimmen Sie alle Lösungen der Kongruenz $x^2 \equiv 1 \pmod{8}$ mit $x \in \mathbb{Z}$.