Zum Inhalt springen

Themenbuch

Teilbarkeit

Teiler, Vielfache und kluge Zerlegungen – vom Kekspaket zur Olympiade

VeröffentlichtVersion 1.2.0ca. 280 Seiten

Ein freundlicher Weg von der Definition über Primfaktoren, ggT und kgV bis zu olympiadetauglichen Teilbarkeitsbeweisen. Zuerst verstehen und üben – dann beweisen wie im Wettbewerb.

GrundlagenAufbauFortgeschrittenOlympiade

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. 1
  2. 2
    Faktorisieren und erste Teilbarkeitsbeweise

    baut auf den vorherigen Ideen auf

  3. 3
    Teilerpaare und die Anzahl der Teiler

    baut auf den vorherigen Ideen auf

  4. 4
    Vielfache, Folgen und Intervalle

    baut auf den vorherigen Ideen auf

  5. 5
    Gemeinsame Teiler und der euklidische Algorithmus

    baut auf den vorherigen Ideen auf

  6. 6
    Gemeinsame Vielfache und das kgV

    baut auf den vorherigen Ideen auf

  7. 7
    Primzahlen und Primzahltests

    baut auf den vorherigen Ideen auf

  8. 8
    Primfaktorzerlegung und Exponenten

    baut auf den vorherigen Ideen auf

  9. 9
    Teilbarkeitsregeln im Dezimalsystem

    baut auf den vorherigen Ideen auf

  10. 10
    Kongruenzen und Restklassen

    baut auf den vorherigen Ideen auf

  11. 11
    Lineare diophantische Gleichungen

    baut auf den vorherigen Ideen auf

  12. 12
    Divisibilitätsgleichungen und Faktorpaare

    baut auf den vorherigen Ideen auf

  13. 13
    Parität, Produkte und Nachbarzahlen

    baut auf den vorherigen Ideen auf

  14. 14
    Schubfachprinzip und teilbare Summen

    baut auf den vorherigen Ideen auf

  15. 15
    Methodenwahl und Beweiswerkstatt

    baut auf den vorherigen Ideen auf

  16. 16
    Teilbarkeits-Olympiade

    baut auf den vorherigen Ideen auf

Zentrale Methoden

Teilbarkeit durch einen Quotienten bezeugen

Für aba\mid b eine ganze Zahl kk mit b=akb=ak finden – dein Zeuge im Beweis.

Warum funktioniert sie?

Teilbarkeit heißt: bb besteht aus einer ganzen Anzahl von Paketen der Größe aa. Der ganzzahlige Quotient kk 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 aba\mid b soll sauber verwendet werden.

Vorgehen

  1. 1. Zielgleichung notieren: Für aba\mid b brauchst du b=akb=ak mit kZk\in\mathbb Z.
  2. 2. Zeugen finden: Forme bb so um, dass der Faktor aa sichtbar wird.
  3. 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 n3nn^3-n oder n2+3nn^2+3n treten auf.
  • Nach dem Ausklammern entstehen aufeinanderfolgende Faktoren.
  • Mehrere kleine Teiler (2, 3, …) sollst du kombinieren.

Vorgehen

  1. 1. Ausdruck zerlegen: Klammere aus oder nutze eine passende Identität.
  2. 2. Teiler lokalisieren: Welcher Faktor garantiert den verlangten Teiler?
  3. 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 dad\mid a und dbd\mid b folgern: dd teilt jede ganzzahlige Kombination ra+sbra+sb.

Warum funktioniert sie?

Vielfache desselben Pakets bleiben beim Addieren, Subtrahieren und ganzzahligen Vervielfachen vollständige Pakete – sie bleiben im „dd-Club“.

Erkennungssignale

  • Mehrere Zahlen sind durch denselben Wert teilbar.
  • Summe, Differenz oder gewichtete Kombination sollst du untersuchen.
  • Zwei bekannte Teilbarkeitsaussagen sollen zusammenarbeiten.

Vorgehen

  1. 1. Zeugen einsetzen: Schreibe a=dma=dm und b=dnb=dn.
  2. 2. Gemeinsam ausklammern: Dann ist ra+sb=d(rm+sn)ra+sb=d(rm+sn).
  3. 3. Ganzzahligkeit schließen: Weil rm+snrm+sn ganzzahlig ist, teilt dd 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. 1. Behauptung präzisieren: Markiere Voraussetzungen und behauptete Folgerung.
  2. 2. Kleinen Randfall testen: Suche einfache Zahlen, die alle Voraussetzungen erfüllen.
  3. 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 n>0n>0 jeden Teiler dd mit seinem Partner n/dn/d verbinden und nur bis n\sqrt n 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. 1. Grenze bestimmen: Berechne oder schätze n\sqrt n.
  2. 2. Kleine Kandidaten prüfen: Teste d=1,2,,nd=1,2,\ldots,\lfloor\sqrt n\rfloor.
  3. 3. Partner ergänzen: Zu jedem gefundenen dd gehört der ganzzahlige Partner n/dn/d.
  4. 4. Doppelung vermeiden: Bei d2=nd^2=n 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 dn/dd\leftrightarrow n/d 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. 1. Teiler paaren: Ordne jedem dnd\mid n den Partner n/dn/d zu.
  2. 2. Fixpunkt prüfen: Ein Teiler bleibt genau dann allein, wenn d=n/dd=n/d, also d2=nd^2=n.
  3. 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 akak 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. 1. Allgemeines Vielfaches schreiben: Setze m=akm=ak mit kZk\in\mathbb Z.
  2. 2. Bedingungen übertragen: Übersetze etwa LakUL\le ak\le U in Schranken für kk.
  3. 3. Ganzzahlige Parameter zählen: Liste oder zähle die zulässigen ganzzahligen kk.

Geeignet

  • der Grundwert a0a\ne0 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. 1. Teilerlisten bilden: Bestimme die positiven Teiler beider Zahlen vollständig.
  2. 2. Schnittmenge markieren: Markiere alle Zahlen, die in beiden Listen vorkommen.
  3. 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. 1. Mit Rest teilen: Schreibe a=bq+ra=bq+r mit 0r<b0\le r<b.
  2. 2. Paar ersetzen: Ersetze (a,b)(a,b) durch (b,r)(b,r).
  3. 3. Wiederholen: Fahre fort, bis der Rest 0 ist.
  4. 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. 1. Vielfachenlisten beginnen: Notiere die positiven Vielfachen beider Zahlen in aufsteigender Reihenfolge.
  2. 2. Ersten Treffer finden: Suche die kleinste Zahl, die in beiden Listen steht.
  3. 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 n\sqrt n 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 n1n-1 auskommen.
  • Ein möglicher kleinster Primteiler wird gesucht.

Vorgehen

  1. 1. Grenze bestimmen: Berechne oder schätze n\sqrt n.
  2. 2. Primteiler sammeln: Liste alle Primzahlen pnp\le\sqrt n.
  3. 3. Teilbarkeit prüfen: Teste nn nur auf Teilbarkeit durch diese Primzahlen.
  4. 4. Schluss formulieren: Ohne Treffer ist nn prim; mit Treffer ist nn 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. 1. Kleinsten Primteiler suchen: Teste 2, dann 3, 5, 7 und weitere Primzahlen.
  2. 2. Wiederholt teilen: Teile so oft durch denselben Primteiler, wie die Division aufgeht.
  3. 3. Rest weiter zerlegen: Fahre mit dem nächsten Primteiler fort, bis der Rest 1 ist.
  4. 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 n=p1a1prarn=p_1^{a_1}\cdots p_r^{a_r} für jeden Primfaktor einen Exponenten von 0 bis aia_i 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. 1. Primfaktoren zerlegen: Schreibe n=p1a1prarn=p_1^{a_1}\cdots p_r^{a_r}.
  2. 2. Exponentwahlen zählen: Für pip_i sind die Exponenten 0,1,,ai0,1,\ldots,a_i möglich, also ai+1a_i+1 Wahlen.
  3. 3. Wahlen multiplizieren: Berechne τ(n)=(a1+1)(ar+1)\tau(n)=(a_1+1)\cdots(a_r+1).

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. 1. Primzahlen ausrichten: Schreibe beide Zerlegungen mit denselben Primzahlspalten; fehlende Faktoren erhalten Exponent 0.
  2. 2. Minimum für den ggT: Wähle für jede Primzahl den kleineren Exponenten.
  3. 3. Maximum für das kgV: Wähle für jede Primzahl den größeren Exponenten.
  4. 4. Kontrollieren: Prüfe Teilbarkeit und bei positiven Zahlen ggTkgV=ab\operatorname{ggT}\cdot\operatorname{kgV}=ab.

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 10kq+r10^kq+r schreiben und nur den letzten Block rr prüfen, wenn der Teiler 10k10^k teilt.

Warum funktioniert sie?

Der vordere Teil besteht aus ganzen Blöcken der Größe 10k10^k. Für Teiler von 10k10^k 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. 1. Blocklänge wählen: Finde ein kleines kk mit d10kd\mid10^k.
  2. 2. Zahl zerlegen: Schreibe n=10kq+rn=10^kq+r mit dem letzten kk-stelligen Block rr.
  3. 3. Vorderen Block verwerfen: Weil d10kqd\mid10^kq, gilt dnd\mid n genau dann, wenn drd\mid r.

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 1-1 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. 1. Passende Summe bilden: Nutze für 3 und 9 die Quersumme, für 11 die alternierende Ziffernsumme.
  2. 2. Kleine Zahl prüfen: Teste die entstandene Summe auf Teilbarkeit durch den Zielteiler.
  3. 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 mm 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. 1. Modul festlegen: Schreibe klar, modulo welcher positiven Zahl gerechnet wird.
  2. 2. Reste ersetzen: Ersetze jeden Term durch einen kleinen restgleichen Vertreter.
  3. 3. Erlaubt verknüpfen: Addiere, subtrahiere oder multipliziere die Vertreter.
  4. 4. Standardrest wählen: Reduziere das Ergebnis auf einen Rest zwischen 0 und m1m-1.

Geeignet

  • Addition, Subtraktion oder Multiplikation vorkommen
  • kleine Reste die Rechnung deutlich verkürzen

Reicht nicht

  • durch einen Faktor gekürzt werden soll, der modulo mm nicht invertierbar ist
Potenzreste in Zyklen organisieren

Aufeinanderfolgende Potenzen modulo mm 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. 1. Kleine Potenzen berechnen: Bestimme a,a2,a3,a,a^2,a^3,\ldots modulo mm.
  2. 2. Zyklus erkennen: Stoppe, sobald das Ausgangsmuster wieder beginnt.
  3. 3. Exponent reduzieren: Bestimme die Position des großen Exponenten modulo Zykluslänge.
  4. 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 ggT(c,m)=1\operatorname{ggT}(c,m)=1 eine Bézout-Darstellung nutzen, um aus cacb(modm)ca\equiv cb\pmod m auf ab(modm)a\equiv b\pmod m zu schließen.

Warum funktioniert sie?

Ein zu mm teilerfremder Faktor besitzt modulo mm 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. 1. Teilerfremdheit prüfen: Berechne ggT(c,m)\operatorname{ggT}(c,m).
  2. 2. Bézout-Koeffizienten finden: Bestimme u,vu,v mit uc+vm=1uc+vm=1.
  3. 3. Inverse erkennen: Modulo mm folgt uc1uc\equiv1.
  4. 4. Kürzung ausführen: Multipliziere die Kongruenz mit uu und erhalte ab(modm)a\equiv b\pmod m.

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 aa und bb berechnen und prüfen, ob er die rechte Seite cc teilt.

Warum funktioniert sie?

Jede ganzzahlige Linearkombination von aa und bb 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 ax+by=cax+by=c.

Vorgehen

  1. 1. ggT bestimmen: Berechne g=ggT(a,b)g=\operatorname{ggT}(a,b).
  2. 2. Teilbarkeit prüfen: Falls gcg\nmid c, existiert keine ganzzahlige Lösung.
  3. 3. Koeffizienten reduzieren: Falls gcg\mid c, teile die gesamte Gleichung durch gg.
  4. 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 xyxy 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 b/gb/g und a/g-a/g alle ganzzahligen Lösungen erzeugen.

Warum funktioniert sie?

Wird xx um b/gb/g erhöht und yy gleichzeitig um a/ga/g 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. 1. Erste Lösung finden: Bestimme ein Paar (x0,y0)(x_0,y_0) mit ax0+by0=cax_0+by_0=c.
  2. 2. Allgemeine Form notieren: Setze x=x0+(b/g)tx=x_0+(b/g)t und y=y0(a/g)ty=y_0-(a/g)t mit tZt\in\mathbb Z.
  3. 3. Randbedingungen übertragen: Übersetze etwa x,y0x,y\ge0 in Schranken für tt.
  4. 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 (x0,y0)(x_0,y_0) bekannt ist
  • g=ggT(a,b)g=\operatorname{ggT}(a,b) 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 n+abn+cn+a\mid bn+c.
  • Der Teiler selbst enthält die gesuchte Variable.
  • Eine Polynomdivision hinterlässt einen konstanten Rest.

Vorgehen

  1. 1. Passendes Vielfaches bilden: Multipliziere den variablen Teiler so, dass der führende variable Term übereinstimmt.
  2. 2. Subtrahieren: Ziehe dieses Vielfache vom Dividenden ab.
  3. 3. Konstante Teiler auflisten: Der variable Teiler muss nun einen festen Rest teilen.
  4. 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 UV=NUV=N 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 xy+x+yxy+x+y 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. 1. Passend ergänzen: Füge auf beiden Seiten denselben Term hinzu, der eine Faktorisierung ermöglicht.
  2. 2. Produkt bilden: Schreibe die Gleichung als U(x)V(y)=NU(x)V(y)=N.
  3. 3. Faktorpaare auflisten: Berücksichtige alle zulässigen positiven und gegebenenfalls negativen Teiler von NN.
  4. 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. 1. Zielteiler zerlegen: Schreibe den Zielteiler als Produkt von Primzahlpotenzen.
  2. 2. Vielfache lokalisieren: Finde im Zahlenblock Faktoren, die die benötigten Potenzen liefern.
  3. 3. Faktoren zusammenführen: Begründe, dass die Beiträge gemeinsam im Gesamtprodukt enthalten sind.
  4. 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 kk ist, muss dies deshalb bereits in jedem Faktor einzeln gelten.

Erkennungssignale

  • ggT(a,b)=1\operatorname{ggT}(a,b)=1 ist gegeben.
  • Das Produkt abab ist ein Quadrat, Kubus oder eine höhere Potenz.
  • Eine globale Potenzeigenschaft soll auf einzelne Faktoren übertragen werden.

Vorgehen

  1. 1. Primzahl fixieren: Betrachte einen beliebigen Primteiler eines Faktors.
  2. 2. Teilerfremdheit nutzen: Sein gesamter Exponent im Produkt stammt nur aus diesem einen Faktor.
  3. 3. Exponenteneigenschaft übertragen: Ist das Produkt eine kk-te Potenz, muss dieser Exponent durch kk teilbar sein.
  4. 4. Für alle Primzahlen schließen: Damit ist jeder Faktor selbst eine kk-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 mm in höchstens mm 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. 1. Schubfächer definieren: Verwende die Restklassen 0,1,,m10,1,\ldots,m-1.
  2. 2. Objekte einsortieren: Ordne jede betrachtete Zahl ihrem Rest modulo mm zu.
  3. 3. Kollision erzwingen: Bei mehr als mm Zahlen liegen zwei im selben Fach.
  4. 4. Differenz deuten: Gleiche Reste bedeuten, dass ihre Differenz durch mm 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 nn betrachten; Rest 0 oder zwei gleiche Reste liefern einen zusammenhängenden Block mit durch nn 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. 1. Partialsummen bilden: Setze Sk=a1++akS_k=a_1+\cdots+a_k.
  2. 2. Reste prüfen: Falls ein Sk0S_k\equiv0, ist der Anfangsblock bereits geeignet.
  3. 3. Kollision suchen: Andernfalls erzwingt das Schubfachprinzip zwei gleiche Reste SiSjS_i\equiv S_j.
  4. 4. Differenzblock lesen: Dann ist SjSi=ai+1++ajS_j-S_i=a_{i+1}+\cdots+a_j 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. 1. Ziel klassifizieren: Geht es um Beweis, Existenz, alle Lösungen, einen Rest oder ein Extremum?
  2. 2. Signale markieren: Suche Nachbarzahlen, variable Teiler, große Potenzen, Teilerfremdheit oder viele Objekte.
  3. 3. Darstellung wählen: Entscheide zwischen Faktorisierung, Kongruenzen, Primexponenten, Bézout, Faktorpaare oder Schubfach.
  4. 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. 1. Voraussetzungen prüfen: Wurde jede Annahme verwendet und jeder Definitionsbereich beachtet?
  2. 2. Richtungen prüfen: Sind bei Äquivalenzen und „genau dann“ beide Richtungen bewiesen?
  3. 3. Vollständigkeit prüfen: Sind alle Teiler, Parameterwerte, Reste oder Fälle enthalten?
  4. 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. 1. Endliche Liste annehmen: Nimm an, alle Primzahlen der gewünschten Art seien p1,,pkp_1,\ldots,p_k.
  2. 2. Hilfszahl konstruieren: Bilde aus ihrem Produkt eine Zahl mit gezieltem Rest, etwa 4p1pk14p_1\cdots p_k-1.
  3. 3. Neuen Primteiler finden: Zeige, dass kein gelisteter Primteiler die Hilfszahl teilt.
  4. 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