Themenbuch
Teilbarkeit
Teiler, Vielfache und kluge Zerlegungen – vom Kekspaket zur Olympiade
Ein freundlicher Weg von der Definition über Primfaktoren, ggT und kgV bis zu olympiadetauglichen Teilbarkeitsbeweisen. Zuerst verstehen und üben – dann beweisen wie im Wettbewerb.
Was du lernst
- Teilbarkeitsaussagen sicher lesen und mit ganzzahligen Quotienten beweisen.
- Teilerstrukturen durch Faktorisierung und Primzahlen sichtbar machen.
- ggT, kgV und den euklidischen Algorithmus sicher einsetzen.
- Teilbarkeit mit Restklassen und olympiadetauglichen Beweisstrategien verbinden.
Rahmen
- Lernzeit
- 28 Std. 5 Min.
- Voraussetzungen
- Sicherer Umgang mit ganzen Zahlen · Grundrechenarten und einfache Potenzen · Lust, kurze Begründungen zu schreiben
Im Buch suchen
Finde Kapitel, Lernziele und Methoden.
Inhaltsverzeichnis
Lernkarte
- 1
- 2Faktorisieren und erste Teilbarkeitsbeweise
baut auf den vorherigen Ideen auf
- 3Teilerpaare und die Anzahl der Teiler
baut auf den vorherigen Ideen auf
- 4Vielfache, Folgen und Intervalle
baut auf den vorherigen Ideen auf
- 5Gemeinsame Teiler und der euklidische Algorithmus
baut auf den vorherigen Ideen auf
- 6Gemeinsame Vielfache und das kgV
baut auf den vorherigen Ideen auf
- 7Primzahlen und Primzahltests
baut auf den vorherigen Ideen auf
- 8Primfaktorzerlegung und Exponenten
baut auf den vorherigen Ideen auf
- 9Teilbarkeitsregeln im Dezimalsystem
baut auf den vorherigen Ideen auf
- 10Kongruenzen und Restklassen
baut auf den vorherigen Ideen auf
- 11Lineare diophantische Gleichungen
baut auf den vorherigen Ideen auf
- 12Divisibilitätsgleichungen und Faktorpaare
baut auf den vorherigen Ideen auf
- 13Parität, Produkte und Nachbarzahlen
baut auf den vorherigen Ideen auf
- 14Schubfachprinzip und teilbare Summen
baut auf den vorherigen Ideen auf
- 15Methodenwahl und Beweiswerkstatt
baut auf den vorherigen Ideen auf
- 16Teilbarkeits-Olympiade
baut auf den vorherigen Ideen auf
Zentrale Methoden
Teilbarkeit durch einen Quotienten bezeugen
Für eine ganze Zahl mit finden – dein Zeuge im Beweis.
Warum funktioniert sie?
Teilbarkeit heißt: besteht aus einer ganzen Anzahl von Paketen der Größe . Der ganzzahlige Quotient ist der Zeuge – ohne ihn zählt der Beweis nicht.
Erkennungssignale
- Eine Teilbarkeitsaussage sollst du direkt beweisen.
- Ein Ausdruck enthält einen sichtbaren gemeinsamen Faktor.
- Die Definition von soll sauber verwendet werden.
Vorgehen
- 1. Zielgleichung notieren: Für brauchst du mit .
- 2. Zeugen finden: Forme so um, dass der Faktor sichtbar wird.
- 3. Ganzzahligkeit benennen: Sage ausdrücklich: Der verbleibende Faktor ist ganzzahlig.
Geeignet
- der Quotient unmittelbar ganzzahlig dargestellt werden kann
- allgemeine Teilbarkeitsregeln bewiesen werden
Reicht nicht
- nur Näherungswerte oder nicht-ganzzahlige Quotienten bekannt sind
Für einen Teilbarkeitsbeweis faktorisieren
Ausdruck in Faktoren zerlegen und den verlangten Teiler in den Faktoren sichtbar machen.
Warum funktioniert sie?
In einer Summe kann Teilbarkeit versteckt sein – in einem Produkt wird der benötigte Faktor oft sichtbar (z. B. Nachbarn).
Erkennungssignale
- Polynome wie oder treten auf.
- Nach dem Ausklammern entstehen aufeinanderfolgende Faktoren.
- Mehrere kleine Teiler (2, 3, …) sollst du kombinieren.
Vorgehen
- 1. Ausdruck zerlegen: Klammere aus oder nutze eine passende Identität.
- 2. Teiler lokalisieren: Welcher Faktor garantiert den verlangten Teiler?
- 3. Zeugen formulieren: Schreibe den ganzen Ausdruck als Zielteiler mal ganze Zahl.
Geeignet
- ein gemeinsamer Faktor ausgeklammert werden kann
- Standardidentitäten wie die Differenz von Quadraten helfen
Reicht nicht
- die Faktorisierung keinen Bezug zum Zielteiler herstellt
Teilbarkeit auf Linearkombinationen übertragen
Aus und folgern: teilt jede ganzzahlige Kombination .
Warum funktioniert sie?
Vielfache desselben Pakets bleiben beim Addieren, Subtrahieren und ganzzahligen Vervielfachen vollständige Pakete – sie bleiben im „-Club“.
Erkennungssignale
- Mehrere Zahlen sind durch denselben Wert teilbar.
- Summe, Differenz oder gewichtete Kombination sollst du untersuchen.
- Zwei bekannte Teilbarkeitsaussagen sollen zusammenarbeiten.
Vorgehen
- 1. Zeugen einsetzen: Schreibe und .
- 2. Gemeinsam ausklammern: Dann ist .
- 3. Ganzzahligkeit schließen: Weil ganzzahlig ist, teilt die Kombination.
Geeignet
- alle Koeffizienten ganzzahlig sind
- ein gemeinsamer Teiler der Ausgangszahlen bekannt ist
Reicht nicht
- aus der Teilbarkeit einer Summe rückwärts auf jeden Summanden geschlossen werden soll
Eine falsche Teilbarkeitsaussage widerlegen
Eine Allaussage („immer“) mit einem einzigen Gegenbeispiel widerlegen.
Warum funktioniert sie?
Ein Satz, der „für alle“ verspricht, scheitert an einem Gegenbeispiel. Mehr brauchst du nicht.
Erkennungssignale
- Eine Behauptung enthält „immer“, „für alle“ oder eine fragwürdige Umkehrung.
- Die Aussage wirkt für kleine Spezialfälle richtig, aber nicht strukturell begründet.
Vorgehen
- 1. Behauptung präzisieren: Markiere Voraussetzungen und behauptete Folgerung.
- 2. Kleinen Randfall testen: Suche einfache Zahlen, die alle Voraussetzungen erfüllen.
- 3. Scheitern nachweisen: Zeige durch Quotient oder Rest, dass die Folgerung falsch ist.
Geeignet
- eine allgemeine Behauptung widerlegt werden soll
- eine Umkehrung einer bekannten Regel geprüft wird
Reicht nicht
- eine wahre Aussage allgemein bewiesen werden muss
Teiler systematisch in Paaren finden
Für jeden Teiler mit seinem Partner verbinden und nur bis suchen.
Warum funktioniert sie?
Kleine Teiler kommen mit großen Partnern. Sobald der kleine Faktor die Quadratwurzel überschreitet, wurden alle Paare bereits in umgekehrter Reihenfolge gesehen.
Erkennungssignale
- Alle positiven Teiler einer konkreten Zahl werden gesucht.
- Die Vollständigkeit einer Teilerliste muss begründet werden.
- Eine Zahl soll auf Quadrateigenschaft untersucht werden.
Vorgehen
- 1. Grenze bestimmen: Berechne oder schätze .
- 2. Kleine Kandidaten prüfen: Teste .
- 3. Partner ergänzen: Zu jedem gefundenen gehört der ganzzahlige Partner .
- 4. Doppelung vermeiden: Bei wird der mittlere Teiler nur einmal gezählt.
Geeignet
- eine konkrete Zahl ohne vollständige Primfaktorzerlegung untersucht wird
- Teilerpaare oder die Teileranzahl gefragt sind
Reicht nicht
- sehr große Zahlen effizient faktorisiert werden müssen
Die Parität der Teileranzahl durch Paarung bestimmen
Teiler über paaren und erkennen, dass nur bei Quadratzahlen ein ungepaarter mittlerer Teiler bleibt.
Warum funktioniert sie?
Fast jeder positive Teiler besitzt einen verschiedenen Partner. Nur die Quadratwurzel kann mit ihrem Partner identisch sein.
Erkennungssignale
- Es wird gefragt, ob eine Zahl gerade oder ungerade viele Teiler hat.
- Quadratzahlen sollen über ihre Teilerstruktur charakterisiert werden.
Vorgehen
- 1. Teiler paaren: Ordne jedem den Partner zu.
- 2. Fixpunkt prüfen: Ein Teiler bleibt genau dann allein, wenn , also .
- 3. Parität schließen: Ohne Fixpunkt ist die Teilerzahl gerade, mit genau einem Fixpunkt ungerade.
Geeignet
- nur die Parität der Teileranzahl statt ihrer exakten Größe benötigt wird
Reicht nicht
- die genaue Teileranzahl einer großen Zahl gesucht ist und Primfaktorzerlegung verfügbar ist
Vielfache als $ak$ parametrisieren
Alle Vielfachen einer Zahl durch einen ganzzahligen Parameter beschreiben und Bedingungen in Schranken für diesen Parameter übersetzen.
Warum funktioniert sie?
Statt unendlich viele Vielfache einzeln aufzulisten, beschreibt die ganze Folge mit einer einzigen Variablen.
Erkennungssignale
- Vielfache in einem Intervall werden gesucht.
- Eine Anzahl von Vielfachen soll bestimmt werden.
- Mehrere aufeinanderfolgende Vielfache treten auf.
Vorgehen
- 1. Allgemeines Vielfaches schreiben: Setze mit .
- 2. Bedingungen übertragen: Übersetze etwa in Schranken für .
- 3. Ganzzahlige Parameter zählen: Liste oder zähle die zulässigen ganzzahligen .
Geeignet
- der Grundwert feststeht
- Intervall- oder Abstandsbedingungen vorliegen
Reicht nicht
- gemeinsame kleinste Vielfache mehrerer Zahlen optimiert werden sollen; dafür folgt später das kgV
Den ggT über gemeinsame Teiler bestimmen
Die positiven Teiler beider Zahlen vergleichen und den größten gemeinsamen Teiler auswählen.
Warum funktioniert sie?
Der ggT ist die größte Paketgröße, mit der sich beide Zahlen ohne Rest in gleich große Pakete zerlegen lassen.
Erkennungssignale
- Zwei überschaubare Zahlen sollen in größtmögliche gleich große Gruppen zerlegt werden.
- Alle gemeinsamen Teiler oder der größte gemeinsame Teiler werden gesucht.
- Die Teilerlisten sind kurz genug, um sie vollständig aufzuschreiben.
Vorgehen
- 1. Teilerlisten bilden: Bestimme die positiven Teiler beider Zahlen vollständig.
- 2. Schnittmenge markieren: Markiere alle Zahlen, die in beiden Listen vorkommen.
- 3. Größten auswählen: Der größte gemeinsame Eintrag ist der ggT.
Geeignet
- die Zahlen klein sind und ihre Teiler schnell aufgelistet werden können
- die Bedeutung des ggT erklärt oder kontrolliert werden soll
Reicht nicht
- die Zahlen groß sind; dann ist der euklidische Algorithmus meist effizienter
Den ggT mit dem euklidischen Algorithmus bestimmen
Die größere Zahl wiederholt durch die kleinere teilen und durch den Rest ersetzen, bis der Rest 0 ist.
Warum funktioniert sie?
Gemeinsame Teiler ändern sich nicht, wenn von einer Zahl ein ganzzahliges Vielfaches der anderen abgezogen wird. Die Zahlen werden dadurch schnell kleiner.
Erkennungssignale
- Der ggT zweier größerer Zahlen wird gesucht.
- Wiederholte Division mit Rest verkleinert das Zahlenpaar.
- Eine Teilbarkeitsaufgabe enthält Ausdrücke, deren Differenz einfacher ist.
Vorgehen
- 1. Mit Rest teilen: Schreibe mit .
- 2. Paar ersetzen: Ersetze durch .
- 3. Wiederholen: Fahre fort, bis der Rest 0 ist.
- 4. Letzten Rest lesen: Der letzte von 0 verschiedene Rest ist der ggT.
Geeignet
- der ggT effizient und ohne vollständige Faktorisierung bestimmt werden soll
- Teilerfremdheit nachgewiesen werden soll
Reicht nicht
- alle einzelnen gemeinsamen Teiler ausdrücklich aufgelistet werden müssen
Das kgV über gemeinsame Vielfache bestimmen
Die positiven Vielfachen beider Zahlen vergleichen und den kleinsten gemeinsamen Treffer auswählen.
Warum funktioniert sie?
Das kgV ist der erste positive Zeitpunkt oder die kleinste positive Menge, an der zwei regelmäßige Rhythmen wieder zusammentreffen.
Erkennungssignale
- Der kleinste gemeinsame Rhythmus, Termin oder Nenner wird gesucht.
- Eine positive Zahl soll durch mehrere Zahlen gleichzeitig teilbar sein.
- Gemeinsame Vielfachenlisten besitzen einen ersten Treffer.
Vorgehen
- 1. Vielfachenlisten beginnen: Notiere die positiven Vielfachen beider Zahlen in aufsteigender Reihenfolge.
- 2. Ersten Treffer finden: Suche die kleinste Zahl, die in beiden Listen steht.
- 3. Minimalität begründen: Zeige, dass vorher kein gemeinsamer positiver Treffer auftritt.
Geeignet
- die Zahlen klein sind oder eine anschauliche Kontrolle benötigt wird
- periodische Vorgänge gleichzeitig eintreten sollen
Reicht nicht
- sehr große Zahlen vorliegen; dann helfen der ggT oder die Primfaktorzerlegung
Eine Primzahl bis zur Quadratwurzel testen
Nur Primteiler bis prüfen, weil jeder zusammengesetzte Wert einen Faktor in diesem Bereich besitzt.
Warum funktioniert sie?
In jedem Faktorpaar liegt mindestens ein Faktor auf der kleinen Seite der Quadratwurzel. Findet sich dort kein Teiler, kann es auch auf der großen Seite keinen neuen geben.
Erkennungssignale
- Eine konkrete positive Zahl soll als prim oder zusammengesetzt erkannt werden.
- Ein vollständiger Primzahltest soll ohne alle Zahlen bis auskommen.
- Ein möglicher kleinster Primteiler wird gesucht.
Vorgehen
- 1. Grenze bestimmen: Berechne oder schätze .
- 2. Primteiler sammeln: Liste alle Primzahlen .
- 3. Teilbarkeit prüfen: Teste nur auf Teilbarkeit durch diese Primzahlen.
- 4. Schluss formulieren: Ohne Treffer ist prim; mit Treffer ist zusammengesetzt.
Geeignet
- eine einzelne überschaubare Zahl geprüft wird
- die Vollständigkeit des Tests begründet werden muss
Reicht nicht
- sehr viele Primzahlen in einem großen Bereich gesucht werden; dafür sind Siebverfahren geeigneter
Eine Zahl systematisch in Primfaktoren zerlegen
Wiederholt durch den kleinsten möglichen Primteiler dividieren, bis nur noch Primfaktoren übrig sind.
Warum funktioniert sie?
Zusammengesetzte Zahlen lassen sich weiter zerlegen. Primzahlen sind die unzerlegbaren Bausteine, aus denen jede positive Zahl größer als 1 aufgebaut ist.
Erkennungssignale
- Eine Zahl soll vollständig faktorisiert werden.
- Teileranzahl, ggT oder kgV sollen über Exponenten bestimmt werden.
- Eine Teilbarkeitsbedingung verlangt bestimmte Primfaktoren.
Vorgehen
- 1. Kleinsten Primteiler suchen: Teste 2, dann 3, 5, 7 und weitere Primzahlen.
- 2. Wiederholt teilen: Teile so oft durch denselben Primteiler, wie die Division aufgeht.
- 3. Rest weiter zerlegen: Fahre mit dem nächsten Primteiler fort, bis der Rest 1 ist.
- 4. Potenzen notieren: Fasse gleiche Primfaktoren als Potenzen zusammen und multipliziere zur Kontrolle.
Geeignet
- konkrete positive ganze Zahlen untersucht werden
- die Exponenten einzelner Primzahlen wichtig sind
Reicht nicht
- nur der ggT sehr großer Zahlen benötigt wird; Euklid kann schneller sein
Die Teileranzahl aus Primexponenten bestimmen
Bei für jeden Primfaktor einen Exponenten von 0 bis wählen und die Anzahlen multiplizieren.
Warum funktioniert sie?
Jeder positive Teiler entscheidet unabhängig, wie oft er jeden verfügbaren Primfaktor übernimmt. Die Anzahl aller Wahlkombinationen ist das Produkt der Wahlmöglichkeiten.
Erkennungssignale
- Die genaue Anzahl positiver Teiler wird gesucht.
- Eine Zahl ist bereits in Primfaktoren zerlegt.
- Zahlen mit einer vorgegebenen Teileranzahl sollen konstruiert werden.
Vorgehen
- 1. Primfaktoren zerlegen: Schreibe .
- 2. Exponentwahlen zählen: Für sind die Exponenten möglich, also Wahlen.
- 3. Wahlen multiplizieren: Berechne .
Geeignet
- die Primfaktorzerlegung bekannt oder leicht bestimmbar ist
- nicht alle Teiler einzeln aufgelistet werden müssen
Reicht nicht
- die Primfaktorzerlegung einer sehr großen Zahl unbekannt ist
ggT und kgV aus Primexponenten lesen
Für jeden Primfaktor beim ggT den kleineren und beim kgV den größeren Exponenten wählen.
Warum funktioniert sie?
Ein gemeinsamer Teiler darf nur so viele Kopien eines Primfaktors verwenden, wie beide Zahlen besitzen. Ein gemeinsames Vielfaches muss dagegen genug Kopien für beide Zahlen enthalten.
Erkennungssignale
- Primfaktorzerlegungen zweier Zahlen sind bekannt.
- ggT und kgV sollen gleichzeitig berechnet werden.
- Die Produktformel soll strukturell begründet werden.
Vorgehen
- 1. Primzahlen ausrichten: Schreibe beide Zerlegungen mit denselben Primzahlspalten; fehlende Faktoren erhalten Exponent 0.
- 2. Minimum für den ggT: Wähle für jede Primzahl den kleineren Exponenten.
- 3. Maximum für das kgV: Wähle für jede Primzahl den größeren Exponenten.
- 4. Kontrollieren: Prüfe Teilbarkeit und bei positiven Zahlen .
Geeignet
- die Exponenten übersichtlich vorliegen
- Teiler- und Vielfachenbedingungen primweise verglichen werden
Reicht nicht
- nur der ggT großer unfaktorisierter Zahlen gefragt ist; dann ist Euklid effizienter
Teilbarkeit über Endziffern oder Endblöcke prüfen
Die Zahl als schreiben und nur den letzten Block prüfen, wenn der Teiler teilt.
Warum funktioniert sie?
Der vordere Teil besteht aus ganzen Blöcken der Größe . Für Teiler von kann er keinen neuen Rest erzeugen.
Erkennungssignale
- Teilbarkeit durch 2, 4, 5, 8, 10, 25 oder ähnliche Teiler einer Zehnerpotenz wird geprüft.
- Nur die letzten ein, zwei oder drei Ziffern scheinen relevant zu sein.
- Eine Endstellenregel soll bewiesen statt nur angewendet werden.
Vorgehen
- 1. Blocklänge wählen: Finde ein kleines mit .
- 2. Zahl zerlegen: Schreibe mit dem letzten -stelligen Block .
- 3. Vorderen Block verwerfen: Weil , gilt genau dann, wenn .
Geeignet
- der Zielteiler eine passende Zehnerpotenz teilt
- eine große Dezimalzahl schnell geprüft wird
Reicht nicht
- der Zielteiler keine kleine Zehnerpotenz teilt
Teilbarkeit über Quer- und Wechselsummen prüfen
Die Dezimalstellen gewichten und nutzen, dass Zehnerpotenzen modulo 3 oder 9 wie 1 und modulo 11 abwechselnd wie 1 und wirken.
Warum funktioniert sie?
Für bestimmte Teiler tragen alle Stellen denselben oder abwechselnde Reste bei. Dann kann die lange Zahl durch eine viel kleinere Ziffernsumme ersetzt werden.
Erkennungssignale
- Teilbarkeit durch 3, 9 oder 11 wird gefragt.
- Eine große Zahl ist über ihre Ziffern gegeben.
- Eine unbekannte Ziffer soll eine Teilbarkeitsbedingung erfüllen.
Vorgehen
- 1. Passende Summe bilden: Nutze für 3 und 9 die Quersumme, für 11 die alternierende Ziffernsumme.
- 2. Kleine Zahl prüfen: Teste die entstandene Summe auf Teilbarkeit durch den Zielteiler.
- 3. Gleichen Rest schließen: Begründe über die Stellenwerte, dass Zahl und Summe denselben Rest besitzen.
Geeignet
- der Teiler zu den Resten von 10 besonders gut passt
- Ziffern statt des vollständigen Zahlenwerts bekannt sind
Reicht nicht
- eine Regel für einen beliebigen Teiler ohne passende Stellenwertstruktur gesucht wird
Mit Kongruenzen sicher rechnen
Zahlen durch restgleiche, kleinere Vertreter ersetzen und Kongruenzen addieren, subtrahieren oder multiplizieren.
Warum funktioniert sie?
Modulo interessieren nur die Restklassen. Jede Zahl darf durch einen handlicheren Vertreter derselben Klasse ersetzt werden.
Erkennungssignale
- Nur ein Divisionsrest statt des vollständigen Zahlenwerts wird gesucht.
- Große Summen oder Produkte sollen vereinfacht werden.
- Teilbarkeit lässt sich als Kongruenz zu 0 formulieren.
Vorgehen
- 1. Modul festlegen: Schreibe klar, modulo welcher positiven Zahl gerechnet wird.
- 2. Reste ersetzen: Ersetze jeden Term durch einen kleinen restgleichen Vertreter.
- 3. Erlaubt verknüpfen: Addiere, subtrahiere oder multipliziere die Vertreter.
- 4. Standardrest wählen: Reduziere das Ergebnis auf einen Rest zwischen 0 und .
Geeignet
- Addition, Subtraktion oder Multiplikation vorkommen
- kleine Reste die Rechnung deutlich verkürzen
Reicht nicht
- durch einen Faktor gekürzt werden soll, der modulo nicht invertierbar ist
Potenzreste in Zyklen organisieren
Aufeinanderfolgende Potenzen modulo berechnen, die Wiederholung erkennen und den Exponenten auf die Zykluslänge reduzieren.
Warum funktioniert sie?
Es gibt nur endlich viele mögliche Reste. Bei fortgesetztem Multiplizieren kehren Restmuster wieder und große Exponenten werden zu kleinen Positionsfragen.
Erkennungssignale
- Die letzte Ziffer oder der Rest einer sehr großen Potenz wird gesucht.
- Aufeinanderfolgende Potenzen zeigen ein kurzes wiederkehrendes Muster.
- Der Exponent ist groß, das Modul aber klein.
Vorgehen
- 1. Kleine Potenzen berechnen: Bestimme modulo .
- 2. Zyklus erkennen: Stoppe, sobald das Ausgangsmuster wieder beginnt.
- 3. Exponent reduzieren: Bestimme die Position des großen Exponenten modulo Zykluslänge.
- 4. Rest ablesen: Lies den zugehörigen Rest aus dem Zyklus ab.
Geeignet
- ein kurzer Zyklus direkt erkennbar ist
- nur ein Rest und nicht die vollständige Potenz benötigt wird
Reicht nicht
- Basis und Modul einen komplizierten Vorzyklus erzeugen und ein einfacheres Teilbarkeitsargument vorliegt
Mit Bézout modular kürzen
Bei eine Bézout-Darstellung nutzen, um aus auf zu schließen.
Warum funktioniert sie?
Ein zu teilerfremder Faktor besitzt modulo eine Umkehrung. Erst diese Umkehrung macht eine Kürzung rechtmäßig.
Erkennungssignale
- Auf beiden Seiten einer Kongruenz steht derselbe Faktor.
- Euklids Lemma oder eine lineare Kongruenz sollst du beweisen.
- Eine modulare Division muss gerechtfertigt werden.
Vorgehen
- 1. Teilerfremdheit prüfen: Berechne .
- 2. Bézout-Koeffizienten finden: Bestimme mit .
- 3. Inverse erkennen: Modulo folgt .
- 4. Kürzung ausführen: Multipliziere die Kongruenz mit und erhalte .
Geeignet
- der zu kürzende Faktor und das Modul teilerfremd sind
- Bézout-Koeffizienten durch den erweiterten euklidischen Algorithmus gefunden werden können
Reicht nicht
- der gemeinsame Faktor einen ggT größer als 1 mit dem Modul besitzt
Die Lösbarkeit von $ax+by=c$ prüfen
Den ggT von und berechnen und prüfen, ob er die rechte Seite teilt.
Warum funktioniert sie?
Jede ganzzahlige Linearkombination von und ist ein Vielfaches ihres ggT. Bézout zeigt umgekehrt, dass jedes Vielfache dieses ggT erreichbar ist.
Erkennungssignale
- Eine lineare Gleichung in zwei Variablen soll ganzzahlig gelöst werden.
- Vor dem Suchen einzelner Lösungen ist eine Existenzentscheidung nötig.
- Eine Mengen- oder Münzaufgabe führt auf .
Vorgehen
- 1. ggT bestimmen: Berechne .
- 2. Teilbarkeit prüfen: Falls , existiert keine ganzzahlige Lösung.
- 3. Koeffizienten reduzieren: Falls , teile die gesamte Gleichung durch .
- 4. Lösung konstruieren: Nutze Bézout oder eine passende Kongruenz für eine erste Lösung.
Geeignet
- alle Koeffizienten ganzzahlig sind
- ganzzahlige statt reelle Lösungen gesucht werden
Reicht nicht
- Produkte wie vorkommen und die Gleichung nicht linear ist
Alle Lösungen von $ax+by=c$ parametrisieren
Von einer partikulären Lösung aus in Schritten von und alle ganzzahligen Lösungen erzeugen.
Warum funktioniert sie?
Wird um erhöht und gleichzeitig um verringert, heben sich die Änderungen auf der linken Seite genau auf.
Erkennungssignale
- Nicht nur eine, sondern alle ganzzahligen Lösungen werden verlangt.
- Zusätzliche Bedingungen wie Nichtnegativität oder Schranken müssen berücksichtigt werden.
- Eine bekannte Lösung soll systematisch verschoben werden.
Vorgehen
- 1. Erste Lösung finden: Bestimme ein Paar mit .
- 2. Allgemeine Form notieren: Setze und mit .
- 3. Randbedingungen übertragen: Übersetze etwa in Schranken für .
- 4. Vollständigkeit benennen: Erkläre, dass die Differenz zweier Lösungen die homogene Gleichung erfüllt und daher diese Schrittform besitzt.
Geeignet
- eine erste Lösung bekannt ist
- die rechte Seite teilt
Reicht nicht
- die Gleichung nicht linear ist
Einen variablen Teiler auf eine Konstante reduzieren
Vom zu teilenden Ausdruck ein geeignetes Vielfaches des variablen Teilers abziehen, bis nur eine Konstante bleibt.
Warum funktioniert sie?
Teilt ein Ausdruck zwei Zahlen, so teilt er auch ihre Differenz. Ein geschickt gewähltes Vielfaches lässt die Variable verschwinden und macht aus unendlich vielen Kandidaten endlich viele Teiler.
Erkennungssignale
- Eine Bedingung hat die Form .
- Der Teiler selbst enthält die gesuchte Variable.
- Eine Polynomdivision hinterlässt einen konstanten Rest.
Vorgehen
- 1. Passendes Vielfaches bilden: Multipliziere den variablen Teiler so, dass der führende variable Term übereinstimmt.
- 2. Subtrahieren: Ziehe dieses Vielfache vom Dividenden ab.
- 3. Konstante Teiler auflisten: Der variable Teiler muss nun einen festen Rest teilen.
- 4. Kandidaten zurückübersetzen: Löse für jeden möglichen Teilerwert nach der Variable auf und prüfe Definitionsbedingungen.
Geeignet
- der Dividend durch eine Linearkombination mit dem Teiler stark vereinfacht wird
- anschließend nur endlich viele konstante Teiler geprüft werden müssen
Reicht nicht
- der Rest nach der Reduktion weiterhin gleich kompliziert von der Variable abhängt
Eine ganzzahlige Gleichung in eine Faktorengleichung verwandeln
Terme ergänzen und gruppieren, bis ein Produkt entsteht, dessen ganzzahlige Faktorpaare vollständig aufgelistet werden können.
Warum funktioniert sie?
Eine nichtlineare Gleichung kann unübersichtlich wirken. Ein festes Produkt hat dagegen nur endlich viele ganzzahlige Faktorpaare.
Erkennungssignale
- Terme wie oder ein quadratisches Produkt treten auf.
- Ganzzahlige oder positive Lösungen einer nichtlinearen Gleichung werden gesucht.
- Durch Ergänzen einer Konstanten entsteht eine Produktstruktur.
Vorgehen
- 1. Passend ergänzen: Füge auf beiden Seiten denselben Term hinzu, der eine Faktorisierung ermöglicht.
- 2. Produkt bilden: Schreibe die Gleichung als .
- 3. Faktorpaare auflisten: Berücksichtige alle zulässigen positiven und gegebenenfalls negativen Teiler von .
- 4. Zurückübersetzen: Löse jedes Faktorpaar nach den ursprünglichen Variablen auf und kontrolliere.
Geeignet
- die Gleichung auf ein Produkt mit fester rechter Seite gebracht werden kann
- Faktorpaare vollständig aufzählbar sind
Reicht nicht
- nach der Faktorisierung weiterhin ein variabler Ausdruck auf der rechten Seite steht
Teilbarkeit in aufeinanderfolgenden Faktoren verteilen
In einem Block aufeinanderfolgender Zahlen die benötigten Primfaktoren auf verschiedene Faktoren verteilen.
Warum funktioniert sie?
Aufeinanderfolgende Zahlen durchlaufen alle Restklassen. Daher tauchen Vielfache kleiner Zahlen regelmäßig auf und liefern gemeinsam den gewünschten Teiler.
Erkennungssignale
- Ein Produkt aus aufeinanderfolgenden ganzen Zahlen tritt auf.
- Teilbarkeit durch eine kleine zusammengesetzte Zahl sollst du beweisen.
- Mehrere benötigte Primfaktoren können aus verschiedenen Faktoren stammen.
Vorgehen
- 1. Zielteiler zerlegen: Schreibe den Zielteiler als Produkt von Primzahlpotenzen.
- 2. Vielfache lokalisieren: Finde im Zahlenblock Faktoren, die die benötigten Potenzen liefern.
- 3. Faktoren zusammenführen: Begründe, dass die Beiträge gemeinsam im Gesamtprodukt enthalten sind.
- 4. Unabhängigkeit prüfen: Achte darauf, benötigte Primfaktoren nicht doppelt aus demselben unzureichenden Faktor zu zählen.
Geeignet
- die Blocklänge mindestens so groß wie die relevanten kleinen Teiler ist
- Parität und kleine Restklassen übersichtlich kombiniert werden können
Reicht nicht
- die Faktoren nicht aufeinanderfolgend sind und keine vergleichbare Restklassenabdeckung besitzen
Potenzeigenschaften auf teilerfremde Faktoren aufteilen
Bei teilerfremden Faktoren Primexponenten getrennt betrachten und eine Potenzeigenschaft des Produkts auf jeden Faktor übertragen.
Warum funktioniert sie?
Teilerfremde Zahlen teilen keine Primbausteine. Wenn im Produkt jeder Primexponent ein Vielfaches von ist, muss dies deshalb bereits in jedem Faktor einzeln gelten.
Erkennungssignale
- ist gegeben.
- Das Produkt ist ein Quadrat, Kubus oder eine höhere Potenz.
- Eine globale Potenzeigenschaft soll auf einzelne Faktoren übertragen werden.
Vorgehen
- 1. Primzahl fixieren: Betrachte einen beliebigen Primteiler eines Faktors.
- 2. Teilerfremdheit nutzen: Sein gesamter Exponent im Produkt stammt nur aus diesem einen Faktor.
- 3. Exponenteneigenschaft übertragen: Ist das Produkt eine -te Potenz, muss dieser Exponent durch teilbar sein.
- 4. Für alle Primzahlen schließen: Damit ist jeder Faktor selbst eine -te Potenz.
Geeignet
- die Faktoren teilerfremd sind
- die Aussage über Primexponenten formuliert werden kann
Reicht nicht
- die Faktoren gemeinsame Primteiler besitzen; dann können sich Exponenten gegenseitig ergänzen
Das Schubfachprinzip auf Restklassen anwenden
Objekte nach ihren Resten modulo in höchstens Schubfächer verteilen und aus einer Kollision eine teilbare Differenz gewinnen.
Warum funktioniert sie?
Zwei Zahlen im selben Restfach unterscheiden sich um ein Vielfaches des Moduls. Mehr Zahlen als Restklassen erzwingen daher eine solche Differenz.
Erkennungssignale
- Aus vielen ganzen Zahlen soll ein Paar mit teilbarer Differenz gefunden werden.
- Die konkrete Auswahl ist unbekannt, aber ihre Größe ist groß genug.
- Es gibt weniger mögliche Reste als betrachtete Zahlen.
Vorgehen
- 1. Schubfächer definieren: Verwende die Restklassen .
- 2. Objekte einsortieren: Ordne jede betrachtete Zahl ihrem Rest modulo zu.
- 3. Kollision erzwingen: Bei mehr als Zahlen liegen zwei im selben Fach.
- 4. Differenz deuten: Gleiche Reste bedeuten, dass ihre Differenz durch teilbar ist.
Geeignet
- eine Existenzbehauptung statt einer konkreten Konstruktion gefragt ist
- Restklassen natürliche Kategorien bilden
Reicht nicht
- nicht mehr Objekte als mögliche Restklassen vorhanden sind und keine zusätzliche Struktur genutzt wird
Teilbare Teilblöcke über Partialsummen finden
Partialsummen modulo betrachten; Rest 0 oder zwei gleiche Reste liefern einen zusammenhängenden Block mit durch teilbarer Summe.
Warum funktioniert sie?
Die Differenz zweier Partialsummen ist genau die Summe der dazwischenliegenden aufeinanderfolgenden Glieder.
Erkennungssignale
- In einer Zahlenfolge wird ein nichtleerer zusammenhängender Block gesucht.
- Die Blocksumme soll durch die Anzahl der Glieder oder ein festes Modul teilbar sein.
- Direktes Durchprobieren aller Intervalle wäre unübersichtlich.
Vorgehen
- 1. Partialsummen bilden: Setze .
- 2. Reste prüfen: Falls ein , ist der Anfangsblock bereits geeignet.
- 3. Kollision suchen: Andernfalls erzwingt das Schubfachprinzip zwei gleiche Reste .
- 4. Differenzblock lesen: Dann ist durch das Modul teilbar.
Geeignet
- zusammenhängende Teilsummen gefragt sind
- genügend viele Partialsummen für eine Restkollision vorliegen
Reicht nicht
- beliebige, nicht zusammenhängende Teilmengen verlangt werden
Die passende Teilbarkeitsmethode auswählen
Aufgabensignale systematisch lesen und vor dem Rechnen eine Hauptmethode sowie eine Kontrollmethode festlegen.
Warum funktioniert sie?
Olympiadeaufgaben wirken oft neu, kombinieren aber bekannte Strukturen. Die richtige Darstellung – Faktoren, Reste, ggT, Primexponenten oder Partialsummen – entscheidet meist mehr als langes Rechnen.
Erkennungssignale
- Mehrere bekannte Methoden scheinen möglich.
- Die Aufgabe enthält noch keine offensichtliche Rechenrichtung.
- Ein vollständiger Lösungsplan soll vor Detailrechnungen entstehen.
Vorgehen
- 1. Ziel klassifizieren: Geht es um Beweis, Existenz, alle Lösungen, einen Rest oder ein Extremum?
- 2. Signale markieren: Suche Nachbarzahlen, variable Teiler, große Potenzen, Teilerfremdheit oder viele Objekte.
- 3. Darstellung wählen: Entscheide zwischen Faktorisierung, Kongruenzen, Primexponenten, Bézout, Faktorpaare oder Schubfach.
- 4. Kontrolle planen: Lege eine zweite Sicht für Probe, Vollständigkeit oder Plausibilität fest.
Geeignet
- gemischte oder olympiadetypische Aufgaben vorliegen
- eine Methode anhand struktureller Signale gewählt werden muss
Reicht nicht
- eine Routineaufgabe die verlangte Methode bereits ausdrücklich nennt
Einen Teilbarkeitsbeweis auf Vollständigkeit prüfen
Voraussetzungen, Äquivalenzen, Kandidatenvollständigkeit und Schlussfolgerung in einem fertigen Beweis systematisch kontrollieren.
Warum funktioniert sie?
Eine richtige Idee kann durch eine fehlende Richtung, einen vergessenen Teiler oder unzulässiges Kürzen unvollständig bleiben. Ein Beweisaudit trennt Entdeckung und Darstellung.
Erkennungssignale
- Eine Lösung ist gefunden, soll aber wettbewerbsreif formuliert werden.
- Alle Lösungen oder ein „genau dann“ werden verlangt.
- Mehrere Teilbarkeitsaussagen wurden kombiniert.
Vorgehen
- 1. Voraussetzungen prüfen: Wurde jede Annahme verwendet und jeder Definitionsbereich beachtet?
- 2. Richtungen prüfen: Sind bei Äquivalenzen und „genau dann“ beide Richtungen bewiesen?
- 3. Vollständigkeit prüfen: Sind alle Teiler, Parameterwerte, Reste oder Fälle enthalten?
- 4. Schluss schließen: Steht eine explizite Antwort oder die genaue behauptete Teilbarkeit am Ende?
Geeignet
- eine vollständige schriftliche Olympiadelösung abgegeben werden soll
- Kandidaten oder Fallunterscheidungen auf Lücken geprüft werden müssen
Reicht nicht
- noch keine tragfähige Lösungsidee vorhanden ist
Neue Primteiler durch eine Produktkonstruktion erzwingen
Aus einer angeblich vollständigen Primzahlliste eine Zahl bauen, deren Primteiler nicht in der Liste liegen und eine gewünschte Restklasseneigenschaft erfüllen.
Warum funktioniert sie?
Ein Produkt bekannter Primzahlen trägt alle bisherigen Teiler. Ein gezieltes Plus oder Minus erzeugt eine Zahl, die von keinem von ihnen geteilt wird und deren Gesamtrest neue Primteiler einschränkt.
Erkennungssignale
- Unendlich viele Primzahlen mit einer bestimmten Restklasseneigenschaft sollen bewiesen werden.
- Euklids Produkt-plus-1-Idee lässt sich anpassen.
- Aus dem Rest eines Produkts soll auf mindestens einen Faktorrest geschlossen werden.
Vorgehen
- 1. Endliche Liste annehmen: Nimm an, alle Primzahlen der gewünschten Art seien .
- 2. Hilfszahl konstruieren: Bilde aus ihrem Produkt eine Zahl mit gezieltem Rest, etwa .
- 3. Neuen Primteiler finden: Zeige, dass kein gelisteter Primteiler die Hilfszahl teilt.
- 4. Restklasse erzwingen: Begründe, dass mindestens ein Primteiler der Hilfszahl die gewünschte Restklasse besitzt.
Geeignet
- die gewünschte Restklasse unter Multiplikation kontrollierbar ist
- ein Widerspruch aus einer endlichen Primzahlliste aufgebaut wird
Reicht nicht
- die Restklasseneigenschaft von Faktoren nicht aus dem Produktrest erschlossen werden kann