Variable Teiler und Faktorisierung

Kongruenzen, Teilbarkeit und Faktorisierung · Abschnitt 51 von 64

Gelöstes Beispiel

Der Teiler n plus drei

Modulo $n+3$ gilt $n\equiv-3$ . Deshalb wird $n^2+5n+11$ zum konstanten Rest 5, und die ursprüngliche Bedingung reduziert sich auf $n+3\mid5$ .

Satz

Polynomrestsatz in modularer Sprache

Für jedes $P\in\mathbb Z[x]$ gilt $P(n)\equiv P(-c)\pmod{n+c}$ . Daher ist $n+c\mid P(n)$ genau dann, wenn $n+c\mid P(-c)$ .

Strategie

Vor oder nach dem Modulo faktorisieren

Faktorisierung kann Primfaktoren und Nachbarzahlen sichtbar machen; Kongruenzen verteilen diese Faktoren anschließend auf Restklassen. Die Reihenfolge wird nach der klareren Struktur gewählt.

Entscheidungsweg

Welche Hauptmethode?

1
Variabler linearer Teiler → konstanten Polynomrest bilden.
2
Produkt aufeinanderfolgender Zahlen → Primfaktoren im Block lokalisieren.
3
Ausdruck $n^N-n$ → Fermat primfaktorweise prüfen.
4
Einfacher Rest der Variablen → direkt ins Polynom einsetzen.
5
Differenz von Potenzen → zuerst faktorisieren.