Woche 5 – Rechnen Modulo n und Restklassen

Was war modulo rechnen nochmal?

1. Modulo rechnen wird häufig als Rechnen mit Rest bezeichnet. Welche Beispiele kennst Du aus Deinem Leben, bei denen Du modulo rechnest?
2. Wie ist \(a \equiv b \mod n\) definiert?
3. Was ist \(12 \mod 8\)?
4. Wie verhält sich der Rest, wenn man Zahlen addiert/subtrahiert? Wie sieht das beispielsweise bei \(7 + 9 \mod 4\) aus?

Restklassen, Inverse und co.

1. Wie waren nochmal Äquivalenzklassen für Äquivalenzrelationen definiert?
2. Ist modulo rechnen eine Äquivalenzrelation? Warum?
3. Angenommen, der \(ggT(x, n)=1\). Warum kann ich dann fuer \(x\) ein Inverses modulo \(n\) berechnen$
4. Warum kann ich kein Inverses berechnen, wenn \(ggT(x, n) \neq 1\)?
5. Sei nun \(n=7\).
   1. Welche Elemente sind in der Restklasse \([3]\) enthalten?
   2. Berechne das Inverse von \(3\).
6. Sei nun \(n=8\)
   1. Welche Elemente sind in der Restklasse \([-1]\) enthalten?
   2. Entscheide fuer die folgenden Werte, ob diese ein Inverses besitzen. Begruende, warum. \(\{2, 4, 5\}\).

Rechenaufgaben

1. Ist \(2^{10000}\) durch \(3\) teilbar?
2. Berechne das letzte Bit von \(7^{1000}\).
3. Sei \(k\) eine ungerade Zahl. Welchen Wert hat \(1^{k} + 2^{k} + 3^{k} + 4^{k} + 5^{k} \mod 6\)?