Zum Inhalt springen
Inhaltsverzeichnis öffnen
Kapitel 4Fortgeschritten34 Min.

Training zu linearen Kongruenzen

Lineare Kongruenzen systematisch lösen · Abschnitt 16 von 64

Übungen

Aufgabe

Zwei Lösungsklassen

Aufbau9 Min.

Löse 6x8(mod14)6x\equiv8\pmod{14} und gib alle Lösungen modulo 14 an.

Aufgabe

Eine unlösbare Kongruenz

Grundlagen5 Min.

Entscheide, ob 6x5(mod14)6x\equiv5\pmod{14} lösbar ist.

Aufgabe

Drei Lösungsklassen

Aufbau10 Min.

Löse 15x21(mod36)15x\equiv21\pmod{36} vollständig.

Aufgabe

Warum genau g Lösungen?

Fortgeschritten14 Min.

Sei g=ggT(a,m)g=\operatorname{ggT}(a,m) und gbg\mid b. Beweise, dass axb(modm)ax\equiv b\pmod m genau gg verschiedene Lösungsklassen modulo mm besitzt.

Aufgabe

Große Zahlen, schnelle Entscheidung

Aufbau7 Min.

Entscheide ohne Restklassentabelle, ob 84x30(mod126)84x\equiv30\pmod{126} lösbar ist.

Aufgabe

Sechs Klassen vollständig finden

Fortgeschritten12 Min.

Löse 18x24(mod42)18x\equiv24\pmod{42} und liste alle Lösungsklassen modulo 42 auf.

Aufgabe

Schritte auf einer Zwölferuhr

Aufbau10 Min.

Ein Zeiger startet bei 0 und springt jeweils 8 Stunden weiter. Nach wie vielen Sprüngen steht er bei 4? Bestimme alle möglichen Sprungzahlen modulo 12.

Aufgabe

Vom Kriterium zur vollständigen Lösung

Olympiade13 Min.6 P.

Finde alle Lösungen von 35x10(mod50)35x\equiv10\pmod{50}.

Zusammenfassung

Existenz, Reduktion, Vollständigkeit

Der ggT entscheidet, ob eine lineare Kongruenz lösbar ist. Bei Lösbarkeit wird durch den ggT einschließlich des Moduls reduziert; die eindeutige reduzierte Klasse erzeugt genau gg Klassen im ursprünglichen Modul.

Checkliste

Selbstkontrolle

  • Berechne ich den ggT von Koeffizient und Modul?

  • Prüfe ich die Teilbarkeit der rechten Seite?

  • Teile ich auch das Modul?

  • Erwarte ich genau gg Lösungsklassen?

  • Hebe ich die reduzierte Klasse vollständig an?