Aufgaben zu Kongruenzen

aus ZUM-Wiki, dem Wiki für Lehr- und Lerninhalte auf ZUM.de
Wechseln zu: Navigation, Suche

Vermischte Aufgaben

  1. Ein wunderbares Beispiel für Modulo-Rechnung ist die Zeit.
    1. Wie viel Uhr ist es in 100 Stunden? In 1000 Stunden? In 10000 Sekunden? Welcher Wochentag ist in 1000000 Tagen?
    2. Wo kommt Modulo-Rechnung noch im Alltag vor?
  2. Untersuchen Sie, welchen Rest Quadratzahlen modulo 8 lassen. Fällt Ihnen etwas auf? Beweisen Sie Ihre Vermutung!
  3. Was ist die letzte Dezimalziffer von 3^1, 3^2, 3^3, 3^4, 3^5, 3^6, ..., 3^{50}, 3^{5000}?
    1. Wie kann man sich der Lösung dieses Problems nähern?
    2. Geben Sie eine Regel an!
    3. Beweisen Sie, dass Ihre Regel gilt.
  4. Wir rechnen modulo n. Man sagt: Zu einem Element a ist das Element b invers genau dann, wenn a\cdot b \equiv 1 mod n.
    1. Suchen Sie zu verschiedenen n und a das inverse Element b zu a.
    2. Für welche a gibt es bei einem gegebenen n kein Inverses?
    3. Gibt es Elemente n, bei denen es für jedes a<n ein Inverses gibt? Welche sind das?

Ein paar Beweise

Beweisen Sie!

  • 1) \forall m\in \mathbb{N}.\forall a,b\in\mathbb{Z}.\forall n\in\mathbb{N}_0. a\equiv b mod m \Rightarrow a^n \equiv b^n mod m
  • 2) \forall m\in \mathbb{N}.\forall a,b,c,d\in\mathbb{Z}. a\cdot c\equiv b\cdot c mod m \wedge ggT(c,m)=d \Rightarrow a \equiv b mod \frac{m}{d}
  • 3) \forall m\in \mathbb{N}.\forall a,b,c\in\mathbb{Z}. a\cdot c\equiv b\cdot c mod m \wedge ggT(c,m)=1 \Rightarrow a \equiv b mod m

(Lösungen)

Weitere Beweise

Beweise oder widerlege, dass folgendes gilt:
a) a\ \equiv \ b \ (mod\ m) \Rightarrow \ a^2\ \equiv \ b^2 \ (mod\ m)
b) a^2\ \equiv \ b^2 \ (mod\ m) \Rightarrow \ a\ \equiv \ b \ (mod\ m)
c) x \cdot a \equiv x \cdot b \ (mod \ x\cdot m) \Rightarrow\ a \equiv \ b\ (mod\ m)
d) a \equiv b \ (mod\ m) \  \wedge\ d|m mit  d \in \mathbb N \Rightarrow \ a \equiv b\ (mod\ d)
e) a \equiv b \ (mod\ m) \Rightarrow a \equiv b+x\cdot m\ (mod\ m)\ für alle x \in \mathbb Z