Kongruenzen | Vikiddo

Themenbuch

Kongruenzen

Rechnen mit Resten – von der Uhr bis zur Olympiade

VeröffentlichtVersion 1.1.0ca. 317 Seiten

Ein freundlicher Weg von Division mit Rest über Inverse und CRT bis zu olympiadetauglichen Restargumenten. Zuerst verstehen und üben – dann beweisen wie im Wettbewerb.

GrundlagenAufbauFortgeschrittenOlympiade

Buch beginnen

Was du lernst

Restklassen präzise verstehen und für endliche Fallanalysen nutzen.
Kongruenzen sicher umformen und lineare Kongruenzen systematisch lösen.
Große Potenzen durch Zyklen, Fermat und Euler kontrollieren.
Simultane Kongruenzen und olympiadetaugliche Restargumente beherrschen.

Rahmen

Lernzeit: 29 Std. 58 Min.
Voraussetzungen: Sicherer Umgang mit ganzen Zahlen · Grundlagen der Teilbarkeit und Division mit Rest · Lust, kurze Begründungen zu schreiben

Im Buch suchen

Finde Kapitel, Lernziele und Methoden.

Inhaltsverzeichnis

Lernkarte

1
Reste und Restklassen
Fundament
2
Kongruenznotation und sichere Rechenregeln
baut auf den vorherigen Ideen auf
3
Modulare Inverse
baut auf den vorherigen Ideen auf
4
Lineare Kongruenzen systematisch lösen
baut auf den vorherigen Ideen auf
5
Potenzreste schnell berechnen
baut auf den vorherigen Ideen auf
6
Restzyklen, Perioden und Vorperioden
baut auf den vorherigen Ideen auf
7
Fermat und Euler
baut auf den vorherigen Ideen auf
8
Multiplikative Ordnung
baut auf den vorherigen Ideen auf
9
Kongruenzsysteme
baut auf den vorherigen Ideen auf
10
Der chinesische Restsatz
baut auf den vorherigen Ideen auf
11
Quadratische Reste
baut auf den vorherigen Ideen auf
12
Unmöglichkeitsbeweise mit Resten
baut auf den vorherigen Ideen auf
13
Kongruenzen, Teilbarkeit und Faktorisierung
baut auf den vorherigen Ideen auf
14
Schubfachprinzip und modulare Invarianten
baut auf den vorherigen Ideen auf
15
Strategiewahl und Beweiswerkstatt
baut auf den vorherigen Ideen auf
16
Olympiade-Generalprobe
baut auf den vorherigen Ideen auf

Zentrale Methoden

Den Standardrest bestimmen

Eine ganze Zahl eindeutig als $a=qm+r$ mit $0\le r<m$ schreiben.

Warum funktioniert sie?

Der Quotient zählt vollständige Pakete der Größe $m$ ; der Standardrest ist der nichtnegative Teil, der übrig bleibt.

Erkennungssignale

Der Rest einer positiven oder negativen Zahl wird gesucht.
Eine Zahl soll einer Restklasse modulo $m$ zugeordnet werden.
Ein kleiner Vertreter soll eine große Zahl ersetzen.

Vorgehen

1. Passendes Vielfaches wählen: Finde $qm\le a<(q+1)m$ .
2. Rest abziehen: Setze $r=a-qm$ .
3. Bereich prüfen: Kontrolliere $0\le r<m$ .

Geeignet

das Modul $m>0$ feststeht
ein eindeutiger Rest zwischen 0 und $m-1$ benötigt wird

Reicht nicht

nur irgendein kongruenter Vertreter statt des Standardrests gesucht ist

Ganze Zahlen nach Restklassen klassifizieren

Zahlen mit demselben Standardrest modulo $m$ zu einer Klasse zusammenfassen und als $r+mk$ parametrisieren.

Warum funktioniert sie?

Eine Restklasse ist eine unendliche Zahlenspur mit konstantem Abstand $m$ .

Erkennungssignale

Alle Zahlen mit einem bestimmten Rest werden gesucht.
Eine Aussage soll für jeden möglichen Rest bewiesen werden.
Zahlen sollen in endlich viele Fälle zerlegt werden.

Vorgehen

1. Mögliche Reste notieren: Verwende $0,1,\ldots,m-1$ .
2. Klasse parametrisieren: Die Klasse von $r$ besteht aus allen $r+mk$ mit $k\in\mathbb Z$ .
3. Eigenschaft klassenweise prüfen: Ersetze die beliebige Zahl durch $r+mk$ oder prüfe den Restvertreter.

Geeignet

das Verhalten nur vom Rest modulo $m$ abhängt
eine vollständige kleine Fallunterscheidung nützlich ist

Reicht nicht

das gewählte Modul mehr Fälle erzeugt als es vereinfacht

Eine Kongruenz über die Differenz beweisen

Für $a\equiv b\pmod m$ zeigen, dass $m$ die Differenz $a-b$ teilt.

Warum funktioniert sie?

Zwei Zahlen besitzen genau dann denselben Rest, wenn sie sich um eine ganze Anzahl von Modulschritten unterscheiden.

Erkennungssignale

Eine Kongruenz soll direkt bewiesen oder widerlegt werden.
Zwei Ausdrücke werden auf Restgleichheit verglichen.
Die Definition soll statt einer Resttabelle verwendet werden.

Vorgehen

1. Differenz bilden: Berechne $a-b$ .
2. Modul ausklammern: Schreibe $a-b=mk$ mit $k\in\mathbb Z$ .
3. Definition anwenden: Schließe $a\equiv b\pmod m$ .

Geeignet

die Differenz leicht faktorisiert oder als Vielfaches von $m$ geschrieben werden kann
eine allgemeine Kongruenzaussage bewiesen wird

Reicht nicht

nur ein numerischer Standardrest gesucht ist

Kongruenzen addieren und multiplizieren

Terme durch kleine kongruente Vertreter ersetzen und Summen, Differenzen, Produkte sowie Potenzen modulo $m$ berechnen.

Warum funktioniert sie?

Restklassen vertragen Addition und Multiplikation: Der Rest des Ergebnisses hängt nur von den Resten der Eingaben ab.

Erkennungssignale

Nur der Rest einer großen Summe, eines Produkts oder einer Potenz wird gesucht.
Ein Ausdruck enthält Zahlen, die sich leicht modulo $m$ reduzieren lassen.
Eine Rechenregel für Kongruenzen sollst du beweisen.

Vorgehen

1. Modul festhalten: Alle Kongruenzen müssen zunächst dasselbe Modul besitzen.
2. Kleine Vertreter wählen: Ersetze jeden Term durch einen bequemen kongruenten Wert.
3. Erlaubt verknüpfen: Addiere, subtrahiere, multipliziere oder potenziere.
4. Standardrest angeben: Reduziere das Ergebnis auf $0,\ldots,m-1$ .

Geeignet

Addition, Subtraktion, Multiplikation oder nichtnegative Potenzen vorkommen
kleine Restvertreter die Rechnung verkürzen

Reicht nicht

eine Division oder Kürzung ohne bekannte modulare Inverse vorgenommen werden soll

Eine einfache lineare Kongruenz über Restklassen lösen

Für kleines Modul alle Restklassen testen oder ein sichtbares multiplikatives Inverses verwenden.

Warum funktioniert sie?

Eine Kongruenzlösung steht für eine ganze Restklasse. Bei kleinem Modul ist eine vollständige Tabelle bereits ein Beweis.

Erkennungssignale

Eine Gleichung der Form $ax\equiv b\pmod m$ tritt auf.
Das Modul ist klein und alle möglichen Reste sind überschaubar.
Ein Faktor besitzt sichtbar ein Produkt mit Rest 1.

Vorgehen

1. Restklassen festlegen: Teste $x=0,1,\ldots,m-1$ oder suche eine Inverse von $a$ .
2. Treffer sammeln: Notiere alle Reste, die $ax\equiv b$ erfüllen.
3. Als Klasse formulieren: Schreibe jede Lösung als Kongruenzklasse modulo $m$ .

Geeignet

das Modul klein ist
eine erste Einführung in lineare Kongruenzen genügt

Reicht nicht

große Module ein systematisches Inversenverfahren verlangen; dies folgt in Teil II

Invertierbarkeit über den ggT prüfen

Ein Element $a$ besitzt modulo $m$ genau dann eine multiplikative Inverse, wenn $\operatorname{ggT}(a,m)=1$ gilt.

Warum funktioniert sie?

Eine Inverse macht aus einem Produkt mit $a$ den Rest 1. Das ist genau eine Bézout-Darstellung von 1 mit den Zahlen $a$ und $m$ .

Erkennungssignale

Durch einen Faktor soll modular dividiert oder gekürzt werden.
Die Existenz einer modularen Inversen wird gefragt.
Eine Kongruenz $ax\equiv1\pmod m$ tritt auf.

Vorgehen

1. ggT berechnen: Bestimme $g=\operatorname{ggT}(a,m)$ .
2. Kriterium anwenden: Genau bei $g=1$ existiert eine Inverse von $a$ modulo $m$ .
3. Konsequenz nennen: Bei $g>1$ ist $ax\equiv1\pmod m$ unlösbar; bei $g=1$ darf die Inverse konstruiert werden.

Geeignet

vor einer modularen Division die Rechtmäßigkeit geprüft werden muss
Existenz oder Nichtexistenz einer Inversen zu entscheiden ist

Reicht nicht

der ggT zwar 1 ist, aber die konkrete Inverse noch berechnet werden muss

Eine modulare Inverse mit Euklid berechnen

Den euklidischen Algorithmus rückwärts einsetzen, bis $1=ua+vm$ entsteht; dann ist $u$ die Inverse von $a$ modulo $m$ .

Warum funktioniert sie?

Der Bézout-Koeffizient vor $a$ beschreibt, wie oft $a$ genommen werden muss, damit modulo $m$ genau der Rest 1 bleibt.

Erkennungssignale

Eine Inverse ist nicht sofort sichtbar.
Das Modul ist zu groß für bequemes Probieren.
Eine lineare Kongruenz mit teilerfremdem Koeffizienten soll gelöst werden.

Vorgehen

1. Euklid vorwärts: Berechne den ggT durch Divisionen mit Rest.
2. Rückwärts einsetzen: Stelle den Rest 1 als $ua+vm$ dar.
3. Modulo m lesen: Aus $ua+vm=1$ folgt $ua\equiv1\pmod m$ .
4. Standardrest bilden: Reduziere $u$ auf einen Rest zwischen 0 und $m-1$ und kontrolliere das Produkt.

Geeignet

$\operatorname{ggT}(a,m)=1$ gilt
eine konkrete und überprüfbare Inverse benötigt wird

Reicht nicht

$a$ und $m$ nicht teilerfremd sind

Modular rechtmäßig dividieren

Eine Kongruenz mit der Inversen eines teilerfremden Faktors multiplizieren, statt formal zu dividieren.

Warum funktioniert sie?

Modulare Division ist Multiplikation mit einer Inversen. Ohne Inverse kann eine vermeintliche Division Lösungen verlieren oder neue erzeugen.

Erkennungssignale

In $ax\equiv b\pmod m$ ist $a$ teilerfremd zu $m$ .
Ein gemeinsamer Faktor soll aus beiden Seiten entfernt werden.
Eine eindeutige Lösungsklasse wird erwartet.

Vorgehen

1. Invertierbarkeit prüfen: Kontrolliere $\operatorname{ggT}(a,m)=1$ .
2. Inverse bestimmen: Finde $u$ mit $ua\equiv1\pmod m$ .
3. Beide Seiten multiplizieren: Aus $ax\equiv b$ folgt $x\equiv ub\pmod m$ .
4. Probe: Setze den gefundenen Rest in die ursprüngliche Kongruenz ein.

Geeignet

der zu entfernende Faktor modulo $m$ invertierbar ist
die Inverse bereits bekannt oder berechenbar ist

Reicht nicht

der Faktor mit dem Modul einen ggT größer als 1 besitzt; dann muss zuerst die ganze Kongruenz reduziert werden

Eine lineare Kongruenz mit dem ggT-Kriterium entscheiden

$ax\equiv b\pmod m$ ist genau dann lösbar, wenn $\operatorname{ggT}(a,m)$ die Zahl $b$ teilt.

Warum funktioniert sie?

Die Kongruenz bedeutet $ax-my=b$ . Alle linken Seiten sind Vielfache des ggT von $a$ und $m$ ; Bézout zeigt, dass jedes passende Vielfache erreichbar ist.

Erkennungssignale

Eine Kongruenz $ax\equiv b\pmod m$ soll auf Lösbarkeit geprüft werden.
Koeffizient und Modul sind nicht teilerfremd.
Die Anzahl der Lösungsklassen wird gefragt.

Vorgehen

1. ggT bestimmen: Setze $g=\operatorname{ggT}(a,m)$ .
2. Teilbarkeit prüfen: Falls $g\nmid b$ , gibt es keine Lösung.
3. Lösungszahl erkennen: Falls $g\mid b$ , gibt es genau $g$ verschiedene Lösungsklassen modulo $m$ .
4. Zur Lösung reduzieren: Teile $a,b,m$ durch $g$ und löse die reduzierte Kongruenz.

Geeignet

Existenz und Zahl der Lösungen systematisch entschieden werden sollen
eine große Suche über alle Restklassen vermieden werden soll

Reicht nicht

mehrere Kongruenzen gleichzeitig gekoppelt sind; dafür folgt später der chinesische Restsatz

Alle Lösungen einer linearen Kongruenz bestimmen

Den gemeinsamen ggT herausdividieren, die reduzierte Kongruenz mit einer Inversen lösen und die Lösung auf alle Klassen modulo des ursprünglichen Moduls anheben.

Warum funktioniert sie?

Nach der Reduktion bleibt eine eindeutige Klasse modulo $m/g$ . Im ursprünglichen Modul erscheint diese Spur genau $g$ -mal.

Erkennungssignale

$g=\operatorname{ggT}(a,m)$ teilt die rechte Seite.
Nicht nur eine, sondern alle Lösungsklassen modulo $m$ werden verlangt.
Eine reduzierte Kongruenz mit teilerfremdem Koeffizienten entsteht.

Vorgehen

1. Durch den ggT reduzieren: Aus $ax\equiv b\pmod m$ wird $(a/g)x\equiv b/g\pmod{m/g}$ .
2. Reduzierte Klasse lösen: Multipliziere mit der Inversen von $a/g$ modulo $m/g$ .
3. Klassen anheben: Ist $x\equiv x_0\pmod{m/g}$ , so lauten die $g$ Klassen modulo $m$ : $x_0+k(m/g)$ für $k=0,\ldots,g-1$ .
4. Vollständigkeit prüfen: Kontrolliere Zahl und Probe aller Klassen.

Geeignet

eine lösbare lineare Kongruenz vollständig gelöst werden soll
die Ergebnisse als Restklassen modulo $m$ anzugeben sind

Reicht nicht

das ggT-Kriterium bereits Unlösbarkeit zeigt

Potenzen durch wiederholtes Quadrieren berechnen

Die Reste von $a,a^2,a^4,a^8,\ldots$ nacheinander quadrieren und dabei nach jedem Schritt modulo $m$ reduzieren.

Warum funktioniert sie?

Jedes Quadrieren verdoppelt den bereits erreichten Exponenten. So wächst der Exponent sehr schnell, während die Restvertreter klein bleiben.

Erkennungssignale

Eine einzelne große Potenz soll modulo $m$ berechnet werden.
Eine kurze Periode ist nicht bekannt oder soll nicht vorausgesetzt werden.
Der Exponent lässt sich als Summe von Zweierpotenzen schreiben.

Vorgehen

1. Mit der Basis beginnen: Reduziere $a$ modulo $m$ .
2. Fortlaufend quadrieren: Berechne die Reste zu $a^2,a^4,a^8,\ldots$ .
3. Exponenten zerlegen: Schreibe den Zielwert als Summe der benötigten Zweierpotenzen.
4. Ausgewählte Reste multiplizieren: Multipliziere nur die passenden Tabellenwerte und reduziere nach jedem Produkt.

Geeignet

jede Basis und jedes positive Modul zugelassen sind
ein zuverlässiges Rechenverfahren statt einer vermuteten Periode gesucht ist

Reicht nicht

eine bereits bewiesene sehr kurze Periode die Rechnung deutlich schneller macht

Den Exponenten binär zerlegen

Einen Exponenten eindeutig als Summe verschiedener Zweierpotenzen schreiben und die zugehörigen Potenzreste kombinieren.

Warum funktioniert sie?

Die Binärdarstellung ist ein Bauplan: Jede gesetzte Stelle sagt, welcher durch Quadrieren erzeugte Potenzrest in das Produkt gehört.

Erkennungssignale

Eine Tabelle für Exponenten $1,2,4,8,\ldots$ liegt vor.
Der Zielwert soll mit möglichst wenigen Multiplikationen erreicht werden.
Die Korrektheit des schnellen Potenzierens soll erklärt werden.

Vorgehen

1. Zweierpotenzen wählen: Zerlege $n=2^{e_1}+\cdots+2^{e_r}$ .
2. Potenzgesetz anwenden: Schreibe $a^n=a^{2^{e_1}}\cdots a^{2^{e_r}}$ .
3. Tabellenwerte einsetzen: Verwende die durch Quadrieren berechneten Reste.
4. Schrittweise reduzieren: Halte jedes Zwischenprodukt klein.

Geeignet

wiederholtes Quadrieren verwendet wird
ein großer Exponent exakt und ohne Zyklusreduktion verarbeitet werden soll

Reicht nicht

nur eine allgemeine Periodenaussage statt eines konkreten Potenzrests verlangt wird

Endziffern als Kongruenz modellieren

Für die letzten $k$ Dezimalziffern den Standardrest modulo $10^k$ berechnen und mit führenden Nullen auffüllen.

Warum funktioniert sie?

Zwei ganze Zahlen besitzen genau dann dieselben letzten $k$ Ziffern, wenn ihre Differenz durch $10^k$ teilbar ist.

Erkennungssignale

Die letzte Ziffer, die letzten zwei oder drei Ziffern werden gesucht.
Eine große Potenz soll nur am rechten Rand ihrer Dezimaldarstellung untersucht werden.
Ein Rest modulo 10, 100 oder 1000 genügt.

Vorgehen

1. Modul wählen: Nutze für $k$ Endziffern das Modul $10^k$ .
2. Potenzrest berechnen: Verwende Quadrieren oder einen bewiesenen Zyklus.
3. Standardrest bilden: Reduziere auf $0,\ldots,10^k-1$ .
4. Ziffernformat beachten: Schreibe bei Bedarf führende Nullen, etwa 001 für drei Endziffern.

Geeignet

dezimalen Endziffern eine klare modulare Bedeutung gegeben werden soll
wiederholtes Quadrieren oder ein Restzyklus danach die Potenz berechnet

Reicht nicht

führende oder mittlere Ziffern gesucht sind

Einen Restzyklus sicher erkennen

Aufeinanderfolgende Potenzreste berechnen, einen wiederholten Zustand markieren und daraus Vorperiode sowie Periode begründen.

Warum funktioniert sie?

Es gibt nur endlich viele Reste. Sobald derselbe Rest erneut auftritt, erzeugt die Multiplikation mit derselben Basis von dort an dieselbe Zukunft.

Erkennungssignale

Aufeinanderfolgende Potenzen zeigen ein wiederkehrendes Muster.
Viele Exponenten sollen mit derselben Basis und demselben Modul behandelt werden.
Eine Periode soll bewiesen statt nur geraten werden.

Vorgehen

1. Reste fortsetzen: Berechne $a^1,a^2,a^3,\ldots$ modulo $m$ .
2. Erste Wiederholung markieren: Notiere die beiden Exponenten desselben Restes.
3. Periode ablesen: Der Abstand der Exponenten ist eine Periodenlänge ab dem ersten Auftreten.
4. Startpunkt festhalten: Unterscheide eine mögliche Vorperiode vom wiederkehrenden Teil.

Geeignet

das Modul klein genug für eine übersichtliche Resttabelle ist
eine wiederkehrende Restfolge die Exponentenreduktion ermöglicht

Reicht nicht

nur zwei zufällig gleiche Werte ohne Kontrolle der dazwischenliegenden Zustände vorliegen

Einen Exponenten im Restzyklus reduzieren

Bei einem Zyklus ab Exponent $s$ den Abstand $n-s$ modulo der Periodenlänge reduzieren und die richtige Zyklusposition bestimmen.

Warum funktioniert sie?

Nicht der Exponent selbst, sondern seine Position relativ zum Beginn des periodischen Abschnitts entscheidet.

Erkennungssignale

Vorperiode und Periodenlänge sind bekannt.
Eine sehr große Potenz soll über eine kleine Zyklustabelle ausgewertet werden.
Der Randfall Rest 0 bei der Exponentendivision muss korrekt behandelt werden.

Vorgehen

1. Zyklusdaten notieren: Halte Start $s$ und Länge $t$ fest.
2. Vorperiode prüfen: Falls $n<s$ , lies den Rest direkt ab.
3. Abstand reduzieren: Berechne $(n-s)\bmod t$ .
4. Position ablesen: Gehe vom Zyklusstart um den reduzierten Abstand weiter.

Geeignet

der Ziel exponent im periodischen Bereich liegt
die Restfolge und ihr Startpunkt bewiesen sind

Reicht nicht

der Exponent noch in der Vorperiode liegt
eine vermeintliche Periode nur vermutet wurde

Den kleinen Satz von Fermat anwenden

Bei Primzahlmodul $p$ und $p\nmid a$ den Exponenten mit $a^{p-1}\equiv1\pmod p$ modulo $p-1$ reduzieren.

Warum funktioniert sie?

Die Multiplikation der von null verschiedenen Restklassen mit $a$ ordnet dieselben Klassen nur neu an. Ihr Produkt bleibt deshalb kongruent.

Erkennungssignale

Das Modul ist eine Primzahl.
Die Basis ist nicht durch diese Primzahl teilbar.
Eine sehr große Potenz soll modulo der Primzahl berechnet werden.

Vorgehen

1. Primzahl prüfen: Begründe, dass das Modul $p$ prim ist.
2. Basis prüfen: Kontrolliere $p\nmid a$ .
3. Exponent reduzieren: Schreibe $n=q(p-1)+r$ .
4. Kleine Potenz berechnen: Nutze $a^n\equiv a^r\pmod p$ und behandle $r=0$ als Rest 1.

Geeignet

$p$ prim und $\operatorname{ggT}(a,p)=1$ ist
eine Periodenlänge $p-1$ ausreicht

Reicht nicht

das Modul zusammengesetzt ist
die Basis durch $p$ teilbar ist; dann muss der Fall direkt behandelt werden

Die eulersche Phi-Funktion berechnen

Die Anzahl der Restklassen zwischen 1 und $m$ bestimmen, die zu $m$ teilerfremd sind.

Warum funktioniert sie?

Genau die teilerfremden Restklassen besitzen eine multiplikative Inverse. $\varphi(m)$ zählt also die Einheiten modulo $m$ .

Erkennungssignale

Der Satz von Euler soll für ein zusammengesetztes Modul verwendet werden.
Die Anzahl invertierbarer Restklassen wird gesucht.
Eine Primfaktorzerlegung des Moduls liegt vor.

Vorgehen

1. Modul faktorisieren: Bestimme die verschiedenen Primteiler von $m$ .
2. Vielfache ausschließen: Verwende $\varphi(m)=m\prod_{p\mid m}(1-1/p)$ .
3. Plausibilität prüfen: Kontrolliere bei kleinem $m$ durch Auflisten der teilerfremden Reste.

Geeignet

kleine Module direkt ausgezählt werden können
die Formel $\varphi(m)=m\prod_{p\mid m}(1-1/p)$ mit bekannter Primfaktorzerlegung genutzt wird

Reicht nicht

nur eine einzelne kleine Potenz ohne allgemeine Exponentenreduktion berechnet werden soll

Den Satz von Euler anwenden

Bei $\operatorname{ggT}(a,m)=1$ den Exponenten mit $a^{\varphi(m)}\equiv1\pmod m$ modulo $\varphi(m)$ reduzieren.

Warum funktioniert sie?

Multiplikation mit einer invertierbaren Restklasse permutiert alle invertierbaren Restklassen modulo $m$ .

Erkennungssignale

Das Modul ist nicht notwendig prim.
Basis und Modul sind teilerfremd.
Die Phi-Funktion des Moduls ist leicht bestimmbar.

Vorgehen

1. Teilerfremdheit prüfen: Berechne $\operatorname{ggT}(a,m)$ .
2. Phi bestimmen: Berechne $\varphi(m)$ .
3. Exponent zerlegen: Schreibe $n=q\varphi(m)+r$ .
4. Restpotenz auswerten: Nutze $a^n\equiv a^r\pmod m$ .

Geeignet

eine sichere allgemeine Periodenlänge für eine teilerfremde Basis benötigt wird
eine Inverse als $a^{\varphi(m)-1}$ dargestellt werden soll

Reicht nicht

$\operatorname{ggT}(a,m)>1$ gilt
eine deutlich kleinere multiplikative Ordnung bereits bekannt ist

Die multiplikative Ordnung bestimmen

Für teilerfremdes $a$ den kleinsten positiven Exponenten $t$ mit $a^t\equiv1\pmod m$ unter den Teilern von $\varphi(m)$ suchen.

Warum funktioniert sie?

Die Ordnung ist die tatsächliche Zykluslänge der Potenzen von $a$ , nicht nur eine allgemeine obere Schranke.

Erkennungssignale

Die kleinste Potenz mit Rest 1 wird gesucht.
Eine bekannte Euler-Periode soll verkürzt werden.
Eine Potenzkongruenz soll nach dem Exponenten gelöst werden.

Vorgehen

1. Teilerfremdheit prüfen: Kontrolliere $\operatorname{ggT}(a,m)=1$ .
2. Phi und Teiler bestimmen: Liste die positiven Teiler von $\varphi(m)$ aufsteigend.
3. Kandidaten testen: Berechne $a^d\pmod m$ für die Teiler $d$ .
4. Ersten Treffer wählen: Der kleinste Teiler mit Rest 1 ist $\operatorname{ord}_m(a)$ .

Geeignet

$\operatorname{ggT}(a,m)=1$ gilt
die Teiler von $\varphi(m)$ überschaubar sind

Reicht nicht

die Basis nicht invertierbar ist; dann ist die multiplikative Ordnung nicht definiert

Exponenten mit der Ordnung reduzieren

Ist $t=\operatorname{ord}_m(a)$ , dann hängt $a^n\pmod m$ nur von $n\pmod t$ ab.

Warum funktioniert sie?

Die Ordnung ist die kleinste vollständige Runde der Potenzfolge. Jeder Block aus $t$ Exponenten trägt den Faktor $a^t\equiv1$ bei.

Erkennungssignale

Die Ordnung der Basis ist bekannt oder leicht bestimmbar.
Fermat oder Euler liefert eine unnötig große Periode.
Eine Kongruenz der Form $a^x\equiv b\pmod m$ soll nach Exponentenklassen gelöst werden.

Vorgehen

1. Ordnung bestimmen: Finde $t=\operatorname{ord}_m(a)$ .
2. Exponent reduzieren: Berechne $r=n\bmod t$ .
3. Zyklusposition auswerten: Nutze bei $r>0$ die Potenz $a^r$ ; bei $r=0$ den Rest 1.
4. Bei unbekanntem Exponenten vergleichen: Ordne den Zielrest seiner Position im vollständigen Zyklus zu.

Geeignet

Basis und Modul teilerfremd sind
große Exponenten oder Exponentenkongruenzen auftreten

Reicht nicht

eine Vorperiode wegen fehlender Teilerfremdheit berücksichtigt werden muss

Ein Kongruenzsystem durch Einsetzen lösen

Eine Kongruenz als $x=a+mk$ parametrisieren, in die zweite einsetzen und die entstehende lineare Kongruenz für $k$ lösen.

Warum funktioniert sie?

Die erste Bedingung erzeugt eine Zahlenspur. Die zweite Bedingung wählt daraus in regelmäßigen Abständen genau die gemeinsamen Treffer aus.

Erkennungssignale

Zwei Kongruenzen für dieselbe Unbekannte sind gegeben.
Eine Bedingung lässt sich leicht als $x=a+mk$ schreiben.
Auch nicht teilerfremde Module sollen behandelt werden.

Vorgehen

1. Erste Klasse parametrisieren: Schreibe $x=a+mk$ .
2. Einsetzen: Setze in $x\equiv b\pmod n$ ein und erhalte $mk\equiv b-a\pmod n$ .
3. Lineare Kongruenz lösen: Nutze das ggT-Kriterium und bestimme alle Klassen für $k$ .
4. Zurücksetzen und normieren: Berechne $x$ und gib die Klasse modulo $\operatorname{kgV}(m,n)$ an.

Geeignet

ein kleines System transparent von Hand gelöst werden soll
die Verträglichkeit während der Rechnung sichtbar werden soll

Reicht nicht

viele paarweise teilerfremde Kongruenzen mit einer direkten CRT-Konstruktion schneller lösbar sind

Die Verträglichkeit eines Kongruenzsystems prüfen

Das System $x\equiv a\pmod m$ , $x\equiv b\pmod n$ ist genau dann lösbar, wenn $a\equiv b\pmod{\operatorname{ggT}(m,n)}$ .

Warum funktioniert sie?

Jede gemeinsame Lösung macht $a-b$ zu einer Differenz aus einem Vielfachen von $m$ und einem Vielfachen von $n$ . Diese Differenz muss durch den ggT teilbar sein.

Erkennungssignale

Die Module besitzen gemeinsame Teiler.
Vor dem Rechnen soll Existenz oder Unmöglichkeit entschieden werden.
Zwei Restbedingungen scheinen einander zu widersprechen.

Vorgehen

1. ggT berechnen: Setze $g=\operatorname{ggT}(m,n)$ .
2. Reste vergleichen: Prüfe $g\mid(a-b)$ .
3. Entscheidung treffen: Bei fehlender Teilbarkeit ist das System unlösbar; sonst darf konstruiert werden.

Geeignet

zwei Kongruenzen zusammengeführt werden
ein allgemeines System mit nicht notwendig teilerfremden Modulen vorliegt

Reicht nicht

die Kongruenzen verschiedene Unbekannte betreffen

Eine Systemlösung modulo des kgV normieren

Alle gemeinsamen Lösungen zweier kompatibler Kongruenzen als genau eine Restklasse modulo $\operatorname{kgV}(m,n)$ angeben.

Warum funktioniert sie?

Zwei gemeinsame Treffer unterscheiden sich zugleich um ein Vielfaches beider Module, also um ein Vielfaches ihres kleinsten gemeinsamen Vielfachen.

Erkennungssignale

Ein gemeinsamer Treffer wurde bereits gefunden.
Alle Lösungen oder die Eindeutigkeit sollen angegeben werden.
Die Module sind möglicherweise nicht teilerfremd.

Vorgehen

1. Endmodul berechnen: Bestimme $L=\operatorname{kgV}(m,n)$ .
2. Treffer reduzieren: Bilde den Standardrest $x_0$ modulo $L$ .
3. Lösungsklasse formulieren: Schreibe $x\equiv x_0\pmod L$ .
4. Beide Bedingungen prüfen: Setze $x_0$ in die ursprünglichen Kongruenzen ein.

Geeignet

ein kompatibles System aus zwei Kongruenzen abgeschlossen wird
eine gefundene Zahl auf den kleinsten nichtnegativen Vertreter reduziert werden soll

Reicht nicht

noch nicht geprüft wurde, ob überhaupt eine Lösung existiert

Die CRT-Lösung direkt konstruieren

Für paarweise teilerfremde Module $m_i$ mit $M=\prod m_i$ die Gewichte $M_iN_i$ bilden, wobei $M_i=M/m_i$ und $M_iN_i\equiv1\pmod{m_i}$ .

Warum funktioniert sie?

Jedes Gewicht wirkt in genau einer Kongruenz wie 1 und in allen anderen wie 0. Die gewichtete Summe stellt daher alle gewünschten Reste gleichzeitig ein.

Erkennungssignale

Mehrere paarweise teilerfremde Module sind gegeben.
Eine direkte Formel oder ein konstruktiver Beweis des chinesischen Restsatzes wird verlangt.
Die Lösung soll eindeutig modulo dem Produkt sein.

Vorgehen

1. Gesamtmodul bilden: Setze $M=m_1\cdots m_r$ .
2. Teilprodukte bilden: Setze $M_i=M/m_i$ .
3. Inverse bestimmen: Finde $N_i$ mit $M_iN_i\equiv1\pmod{m_i}$ .
4. Gewichtete Summe: Berechne $x_0=\sum a_iM_iN_i$ und reduziere modulo $M$ .

Geeignet

die Module paarweise teilerfremd sind
modulare Inverse der Teilprodukte gut berechnet werden können

Reicht nicht

ein Modulpaar einen ggT größer als 1 besitzt; dann muss zuerst die verallgemeinerte Verträglichkeit geprüft werden

Mehrere Kongruenzen schrittweise zusammenführen

Je zwei Bedingungen zu einer neuen Restklasse verbinden und diese anschließend mit der nächsten Kongruenz kombinieren.

Warum funktioniert sie?

Eine bereits zusammengeführte Klasse fasst alle bisherigen Bedingungen zusammen. Sie kann wie eine einzige neue Kongruenz weiterverwendet werden.

Erkennungssignale

Drei oder mehr Kongruenzen sollen von Hand gelöst werden.
Nicht alle Module sind paarweise teilerfremd.
Die direkte CRT-Summe wäre unübersichtlich.

Vorgehen

1. Erstes Paar lösen: Führe zwei Kongruenzen zu $x\equiv c\pmod L$ zusammen.
2. Neue Bedingung anfügen: Kombiniere diese Klasse mit der nächsten Kongruenz.
3. Verträglichkeit prüfen: Prüfe bei jedem Paar das ggT-Kriterium.
4. Bis zum Ende wiederholen: Normiere die letzte Klasse modulo dem entstandenen kgV.

Geeignet

Systeme gemischter Modulstruktur vorliegen
nach jedem Schritt eine Verträglichkeitsprüfung gewünscht ist

Reicht nicht

eine symbolische CRT-Konstruktionsformel explizit verlangt wird

Eine vollständige Quadratreste-Tabelle erstellen

Die Werte $r^2\pmod m$ für ein vollständiges Restsystem berechnen und die verschiedenen Ergebnisse als Menge sammeln.

Warum funktioniert sie?

Jedes ganzzahlige Quadrat hängt modulo $m$ nur vom Rest seiner Basis ab. Eine endliche Tabelle beschreibt daher alle unendlich vielen Quadrate.

Erkennungssignale

Mögliche oder unmögliche Quadratreste werden gesucht.
Eine quadratische Kongruenz $x^2\equiv a\pmod m$ soll entschieden werden.
Alle Fälle sollen vollständig statt durch Beispiele erfasst werden.

Vorgehen

1. Reste festlegen: Nutze $r=0,1,\ldots,m-1$ oder eine begründete symmetrische Hälfte.
2. Quadrate reduzieren: Berechne jeden Wert $r^2\bmod m$ .
3. Doppelte Werte bündeln: Sammle die verschiedenen Quadratreste als Menge.
4. Vollständigkeit nennen: Begründe, dass jede ganze Zahl zu einem geprüften Rest kongruent ist.

Geeignet

das Modul klein genug für eine übersichtliche Tabelle ist
ein vollständiger Ausschluss oder eine vollständige Lösungsmenge benötigt wird

Reicht nicht

ein großes Primzahlmodul speziellere Werkzeuge wie das Legendre-Symbol erfordern würde

Die Symmetrie von Quadratresten nutzen

Aus $r^2\equiv(-r)^2\pmod m$ paarweise gleiche Tabellenwerte erkennen und bei Primzahlmodul die Anzahl nichtverschwindender Quadratreste bestimmen.

Warum funktioniert sie?

Gegenüberliegende Restklassen besitzen dasselbe Quadrat. Bei einer ungeraden Primzahl sind dies genau die einzigen Doppelungen unter den von null verschiedenen Resten.

Erkennungssignale

Eine Quadratreste-Tabelle soll verkürzt werden.
Die Anzahl quadratischer Reste modulo einer ungeraden Primzahl wird gefragt.
Aus $x^2\equiv y^2$ sollen mögliche Beziehungen zwischen $x$ und $y$ folgen.

Vorgehen

1. Vorzeichen paaren: Ordne $r$ und $m-r$ einander zu.
2. Gleiche Quadrate nutzen: Berechne nur einen Vertreter jedes Paares.
3. Bei Primzahl Eindeutigkeit beweisen: Aus $p\mid(x-y)(x+y)$ folgt $x\equiv y$ oder $x\equiv-y\pmod p$ .
4. Paare zählen: Die $p-1$ Nichtnullreste bilden $(p-1)/2$ Vorzeichenpaare.

Geeignet

Quadrate statt allgemeiner Potenzen betrachtet werden
das Modul eine ungerade Primzahl ist und exakt gezählt werden soll

Reicht nicht

bei zusammengesetztem Modul aus $x^2\equiv y^2$ vorschnell nur $x\equiv\pm y$ geschlossen werden soll

Restmengen von Ausdrücken kombinieren

Mögliche Reste einzelner Terme als Mengen bestimmen und durch Summen, Differenzen oder Produkte zu den möglichen Resten des Gesamtausdrucks verbinden.

Warum funktioniert sie?

Wenn jeder Summand nur wenige Reste annehmen kann, kann auch der ganze Ausdruck nur in einer kleinen endlichen Ergebnismenge liegen.

Erkennungssignale

Eine Gleichung enthält mehrere Quadrate.
Mögliche Reste einer Summe oder Differenz werden gesucht.
Ein Zielrest soll durch vollständige Mengenarithmetik ausgeschlossen werden.

Vorgehen

1. Einzelmengen bestimmen: Notiere für jeden Term seine möglichen Reste.
2. Mengen kombinieren: Bilde alle benötigten Summen, Differenzen oder Produkte modulo $m$ .
3. Doppelte Ergebnisse entfernen: Schreibe die vollständige Ergebnismenge kompakt.
4. Mit dem Ziel vergleichen: Prüfe, ob der verlangte Rest enthalten ist.

Geeignet

die Restmengen der Einzelterme klein sind
eine vollständige Fallkombination überschaubar bleibt

Reicht nicht

das Modul so viele Reste erzeugt, dass die Kombination unübersichtlich wird

Ein sperrendes Modul wählen

Ein kleines Modul suchen, bei dem die vorkommenden Potenzen wenige Reste besitzen und die behauptete Gleichung einen unmöglichen Zielrest erzwingt.

Warum funktioniert sie?

Ein gutes Modul löscht unwichtige Details und behält genau die Struktur, die eine Lösung verhindert.

Erkennungssignale

Eine ganzzahlige Gleichung soll als unlösbar erwiesen werden.
Quadrate, gerade/ungerade Zahlen oder feste Potenzen treten auf.
Direkte Größenabschätzungen helfen nicht.

Vorgehen

1. Struktur lesen: Suche Quadrate, Potenzen, Parität und feste Koeffizienten.
2. Kandidaten testen: Prüfe kleine Module auf möglichst kleine Restmengen.
3. Stärkstes Modul wählen: Nutze das Modul, das den Zielrest vollständig ausschließt.
4. Vollständigkeit beweisen: Nenne alle möglichen Reste und formuliere den Widerspruch.

Geeignet

modulo 4, 8, 3, 5 oder einem anderen kleinen Modul eine starke Einschränkung entsteht
ein einziger lokaler Widerspruch genügt, um globale Lösungen auszuschließen

Reicht nicht

jede Restklasse des Zielmoduls erreichbar bleibt
nur die Existenz einzelner Lösungen statt Unmöglichkeit untersucht wird

Unmöglichkeit durch einen modularen Widerspruch beweisen

Aus einer angenommenen ganzzahligen Lösung eine Kongruenz ableiten, deren linke und rechte Seite in unvereinbaren Restmengen liegen.

Warum funktioniert sie?

Jede ganzzahlige Lösung müsste auch nach Reduktion modulo $m$ eine Lösung bleiben. Scheitert schon diese notwendige Bedingung, kann es keine ganze Lösung geben.

Erkennungssignale

Es soll bewiesen werden, dass keine ganzen oder positiven Lösungen existieren.
Eine Seite der Gleichung besitzt stark eingeschränkte Potenzreste.
Nach einem ersten Widerspruch kann eine Teilbarkeit aller Variablen einen Abstieg auslösen.

Vorgehen

1. Lösung annehmen: Formuliere klar, welche ganzen Zahlen die Gleichung erfüllen sollen.
2. Modulo reduzieren: Ersetze jeden Term durch seine möglichen Reste.
3. Widerspruch oder Teilbarkeit ableiten: Zeige einen unmöglichen Rest oder dass alle Variablen einen gemeinsamen Faktor besitzen.
4. Schluss formulieren: Verwirf die Annahme direkt oder konstruiere beim Abstieg eine kleinere Lösung.

Geeignet

ein Modul einen direkten Widerspruch liefert
eine primitive Lösung oder ein kleinster positiver Wert für unendlichen Abstieg angenommen werden kann

Reicht nicht

die modulare Bedingung nur notwendig, aber nicht widersprüchlich ist

Kongruente Werte in Polynome einsetzen

Aus $a\equiv b\pmod m$ für jedes ganzzahlige Polynom $P$ die Kongruenz $P(a)\equiv P(b)\pmod m$ ableiten.

Warum funktioniert sie?

Polynome entstehen nur durch Addition und Multiplikation. Beide Operationen respektieren Kongruenzen, daher darf ein Argument durch jeden kongruenten Vertreter ersetzt werden.

Erkennungssignale

Ein Polynom soll modulo einer Zahl ausgewertet werden.
Eine Variable besitzt einen einfachen Restvertreter.
Eine allgemeine Teilbarkeitsaussage enthält Potenzen derselben Variablen.

Vorgehen

1. Argument reduzieren: Ersetze $a$ durch einen kleinen kongruenten Vertreter $b$ .
2. Polynom auswerten: Berechne $P(b)$ modulo $m$ .
3. Rechenregeln begründen: Verweise auf Erhaltung durch Summen und Produkte.
4. Teilbarkeit übersetzen: Aus Rest 0 folgt die gewünschte Teilbarkeit.

Geeignet

alle Koeffizienten ganzzahlig sind
ein kleiner Restvertreter die Polynomrechnung vereinfacht

Reicht nicht

Divisionen oder nicht ganzzahlige Operationen im Ausdruck auftreten

Zusammengesetzte Teilbarkeit in teilerfremde Module zerlegen

Für $M=m_1\cdots m_r$ mit paarweise teilerfremden Faktoren die Teilbarkeit durch jedes $m_i$ getrennt beweisen und anschließend zum Produkt zusammensetzen.

Warum funktioniert sie?

Verschiedene Primfaktoren können durch unterschiedliche lokale Gründe entstehen. Erst am Ende werden die unabhängigen Teilbarkeiten kombiniert.

Erkennungssignale

Eine universelle Teilbarkeit durch ein zusammengesetztes Produkt wird verlangt.
Für jeden Primfaktor passt ein kurzer Rest- oder Fermatbeweis.
Produkte aufeinanderfolgender Zahlen treten auf.

Vorgehen

1. Ziel faktorisieren: Zerlege $M$ in paarweise teilerfremde Faktoren.
2. Lokal beweisen: Zeige jeden Faktor durch passende Restklassen, Fermat oder Faktorisierung.
3. Teilerfremdheit nennen: Begründe, dass die Faktoren paarweise teilerfremd sind.
4. Zum Produkt schließen: Folgere $M\mid N$ .

Geeignet

die Zielmoduln paarweise teilerfremd sind
jede lokale Teilbarkeit leichter als die direkte Rechnung modulo dem Produkt ist

Reicht nicht

gemeinsame Primfaktoren zusätzliche Exponenteninformationen erfordern

Einen variablen Teiler auf einen konstanten Rest reduzieren

Bei einer Bedingung $n+c\mid P(n)$ die Kongruenz $n\equiv-c\pmod{n+c}$ einsetzen und so $P(n)$ auf eine Konstante reduzieren.

Warum funktioniert sie?

Modulo des variablen Teilers verhält sich die Variable wie die feste Zahl $-c$ . Der scheinbar große Ausdruck schrumpft auf einen konstanten Rest.

Erkennungssignale

Ein linearer Ausdruck in $n$ soll ein Polynom in $n$ teilen.
Alle positiven ganzen $n$ mit einer Teilbarkeitsbedingung werden gesucht.
Polynomdivision würde einen konstanten Rest liefern.

Vorgehen

1. Modulare Variable ersetzen: Nutze $n\equiv-c\pmod{n+c}$ .
2. Konstanten Rest berechnen: Bestimme $R=P(-c)$ .
3. Teilerbedingung verkleinern: Die Ausgangsbedingung ist äquivalent zu $n+c\mid R$ .
4. Endliche Teiler prüfen: Nutze Vorzeichen- und Bereichsbedingungen für alle möglichen Teiler von $R$ .

Geeignet

der Teiler die Form $n+c$ besitzt
nach Einsetzen von $-c$ eine kleine von $n$ unabhängige Konstante entsteht

Reicht nicht

der reduzierte Rest weiterhin von $n$ abhängt und keine Vereinfachung entsteht

Restklassen als Schubfächer verwenden

Mehr ganze Zahlen oder Partialsummen als verfügbare Restklassen betrachten und dadurch zwei kongruente Werte oder einen Nullrest erzwingen.

Warum funktioniert sie?

Modulo $m$ gibt es nur $m$ Fächer. Werden mehr als $m$ Objekte einsortiert, teilen sich zwei ein Fach; ihre Differenz ist durch $m$ teilbar.

Erkennungssignale

Viele ganze Zahlen sollen ein Paar mit teilbarer Differenz liefern.
Ein nichtleerer Block mit teilbarer Summe wird gesucht.
Nur Existenz, nicht eine konkrete Konstruktion, ist gefragt.

Vorgehen

1. Objekte wählen: Verwende Zahlen, Positionen oder Partialsummen.
2. Restfächer festlegen: Ordne jedes Objekt seinem Rest modulo $m$ zu.
3. Schubfach anwenden: Erzwinge einen Nullrest oder zwei gleiche Reste.
4. Zur Aufgabe zurückübersetzen: Nutze Differenz oder Partialsumme für die verlangte Teilbarkeit.

Geeignet

Objekte natürlich durch Reste klassifiziert werden können
Partialsummen eine Blocksumme als Differenz darstellen

Reicht nicht

zu wenige Objekte für die Zahl der Restklassen vorhanden sind
eine explizite Lösung statt eines Existenzbeweises verlangt wird

Einen modularen Invarianten finden

Eine Zustandsgröße wählen, deren Rest modulo $m$ sich unter jedem erlaubten Zug nicht ändert, und damit unerreichbare Zielzustände ausschließen.

Warum funktioniert sie?

Viele Züge verändern eine Größe, aber immer um ein Vielfaches desselben Moduls. Der genaue Wert bewegt sich, sein Rest bleibt als unsichtbares Etikett erhalten.

Erkennungssignale

Eine Folge erlaubter Operationen soll einen Zielzustand erreichen.
Jeder Zug verändert Summe, Koordinatensumme oder gewichtete Summe regelmäßig.
Unmöglichkeit statt einer konkreten Zugfolge sollst du beweisen.

Vorgehen

1. Zustandsgröße wählen: Teste Summe, Differenz, Koordinatensumme oder gewichtete Summe.
2. Jeden Zug prüfen: Zeige, dass die Änderung stets durch $m$ teilbar ist.
3. Startrest berechnen: Bestimme den invarianten Rest des Anfangszustands.
4. Ziel vergleichen: Ein anderer Zielrest beweist Unerreichbarkeit.

Geeignet

alle erlaubten Züge dieselbe Größe modulo $m$ erhalten
Start und Ziel verschiedene Reste dieser Größe besitzen

Reicht nicht

mindestens ein erlaubter Zug den vorgeschlagenen Rest verändert
gleicher Rest von Start und Ziel die Erreichbarkeit noch nicht garantiert

Die passende Kongruenzstrategie diagnostizieren

Aus Ziel, Ausdrucksform und Nebenbedingungen systematisch Modul und Werkzeug auswählen, bevor gerechnet wird.

Warum funktioniert sie?

Olympiadeaufgaben nennen die Methode selten. Gute Lösungen beginnen deshalb mit einer Diagnose: Geht es um Teilbarkeit, Unmöglichkeit, große Potenzen, mehrere Restbedingungen oder eine erhaltene Zustandsgröße?

Erkennungssignale

Die Aufgabe enthält kein vorgegebenes Modul.
Mehrere bekannte Kongruenzmethoden scheinen zunächst möglich.
Eine kurze Beobachtung kann eine lange Rechnung ersetzen.

Vorgehen

1. Zieltyp bestimmen: Ordne die Aufgabe als Berechnung, Existenz, Vollständigkeit, Teilbarkeit oder Unmöglichkeit ein.
2. Struktursignale markieren: Suche Potenzen, Quadrate, lineare Teiler, mehrere Module, viele Objekte oder erlaubte Züge.
3. Kandidaten testen: Prüfe kleine Module und bekannte Sätze an wenigen Resten, ohne schon den ganzen Beweis zu schreiben.
4. Kürzesten tragfähigen Weg wählen: Entscheide dich für die Methode, die Ziel und Voraussetzungen vollständig verbindet.

Geeignet

eine neue oder gemischte Aufgabe zunächst strukturiert werden muss
Modulwahl und Werkzeugwahl den entscheidenden Lösungsfortschritt bilden

Reicht nicht

das benötigte Verfahren bereits ausdrücklich vorgegeben und direkt anwendbar ist

Voraussetzungen modularer Werkzeuge prüfen

Vor jedem Kürzen, Invertieren oder Exponentenreduzieren die benötigten ggT-, Primzahl- und Teilerfremdheitsbedingungen explizit kontrollieren.

Warum funktioniert sie?

Viele fast richtige Kongruenzlösungen scheitern nicht an der Rechnung, sondern an einem unzulässigen Schritt. Ein kurzer Voraussetzungen-Check schützt den gesamten Beweis.

Erkennungssignale

Ein Faktor soll aus einer Kongruenz gekürzt werden.
Fermat, Euler oder eine multiplikative Ordnung soll verwendet werden.
Eine Lösungsklasse wurde nach Division scheinbar eindeutig.

Vorgehen

1. Geplanten Satz nennen: Formuliere genau, welchen Satz oder welche Kürzungsregel du verwenden willst.
2. Bedingungen auflisten: Notiere Primzahl, Teilerfremdheit, Invertierbarkeit oder ggT-Teilbarkeit.
3. Bedingungen nachweisen: Berechne den ggT oder behandle nicht teilerfremde Fälle getrennt.
4. Erst dann umformen: Führe Kürzung oder Exponentenreduktion aus und behalte alle Lösungsklassen.

Geeignet

eine modulare Division oder ein Potenzsatz eingesetzt wird
die Zahl aller Lösungen einer linearen Kongruenz wichtig ist

Reicht nicht

nur addiert, subtrahiert oder multipliziert wird

Einen Kongruenzbeweis vollständig schließen

Jeden modularen Zwischenschritt zur ursprünglichen Aussage zurückübersetzen und bei Bestimmungsaufgaben Existenz, Vollständigkeit und Probe sichern.

Warum funktioniert sie?

Eine Restrechnung ist erst dann eine Lösung, wenn klar ist, warum sie genau die verlangte Teilbarkeit, Unmöglichkeit oder Gesamtheit aller Lösungen beweist.

Erkennungssignale

Die Aufgabe verlangt einen Beweis und nicht nur einen Rest.
Alle ganzen Zahlen oder alle Lösungsklassen werden gesucht.
Lokale Aussagen zu mehreren Modulen müssen zusammengesetzt werden.

Vorgehen

1. Behauptung präzisieren: Formuliere das Ziel als Teilbarkeit oder als Kongruenz mit genauem Modul.
2. Lückenlose Kette schreiben: Begründe jeden Satz, jede Fallunterscheidung und jede Kombination von Modulen.
3. Vollständigkeit sichern: Zeige bei Lösungsbestimmungen, dass keine weiteren Klassen möglich sind.
4. Zur Aufgabe zurückkehren: Schließe mit einem Satz, der das modulare Ergebnis in der Sprache der Aufgabe ausdrückt.

Geeignet

ein Ergebnis als vollständiger Olympiadebeweis formuliert werden soll
notwendige und hinreichende Bedingungen unterschieden werden müssen

Reicht nicht

nur eine kurze numerische Restberechnung verlangt ist

Kongruenzaufgaben unter Wettbewerbsbedingungen bearbeiten

Aufgaben sichten, sichere Punkte zuerst gewinnen, Sackgassen begrenzen und vor Abgabe einen gezielten Beweischeck durchführen.

Warum funktioniert sie?

Im Wettbewerb zählt nicht nur, eine Idee zu haben. Zeit, Darstellung und Kontrolle entscheiden, ob aus der Idee tatsächlich Punkte werden.

Erkennungssignale

Mehrere unterschiedlich schwere Aufgaben stehen unter Zeitdruck zur Auswahl.
Eine Lösungsidee ist vorhanden, aber noch nicht sauber ausformuliert.
Ein Ergebnis muss vor der Abgabe effizient kontrolliert werden.

Vorgehen

1. Sichten: Markiere in wenigen Minuten sichere, mögliche und zunächst offene Aufgaben.
2. Punkte sichern: Bearbeite zuerst Aufgaben mit klarer Strategie und vollständigem Abschluss.
3. Sackgassen begrenzen: Wechsle nach einem festgelegten Zeitfenster und notiere den bisherigen Ansatz.
4. Abgabe prüfen: Kontrolliere Voraussetzungen, Restrechnungen, Vollständigkeit und den letzten Schlusssatz.

Geeignet

ein gemischter Trainingssatz oder eine echte Wettbewerbsklausur bearbeitet wird
Zeitbudget und Punkteverteilung berücksichtigt werden sollen

Reicht nicht

ein einzelner Begriff ohne Zeitdruck neu gelernt wird