Satz von Lucas

Der Satz von Lucas ist der klassische Weg, einen Binomialkoeffizienten modulo einer Primzahl auszuwerten, wenn n so groß ist, dass die Fakultät von n unpraktikabel wird. Wettbewerbsprogrammierung, kombinatorische Zahlentheorie und Kryptographie-Hausaufgaben brauchen diese Reduktion, wenn direkte Fakultäten überlaufen oder zu teuer werden.

Was der Satz von Lucas besagt und wann Sie ihn brauchen

In der elementaren Kombinatorik zählt der Binomialkoeffizient C(n, k) die k-elementigen Teilmengen einer n-elementigen Menge und entspricht der Fakultät von n geteilt durch die Fakultät von k mal die Fakultät von (n minus k). Diese geschlossene Form wird unbrauchbar, sobald n einige Tausend überschreitet und Sie nur die Antwort modulo einer kleinen Primzahl brauchen: die Zwischenfakultäten explodieren, und Gleitkomma-Näherungen verlieren den exakten Rest. Der Satz von Lucas, benannt nach Édouard Lucas, löst genau dieses modulare Problem.

Jeder Faktor nutzt Argumente kleiner als p und lässt sich mit einer kurzen multiplikativen Schleife und modularen Inversen berechnen, die existieren, weil p prim ist und jeder Nenner kleiner als p ist. Allein dieser Test beantwortet viele Fragen der Art „ist der Binomialkoeffizient durch diese Primzahl teilbar?“ ohne ein volles Produkt zu berechnen.

Der Satz verlangt, dass p prim ist; für zusammengesetzte Moduln ist dasselbe Ziffernprodukt im Allgemeinen ungültig, und diese Fähigkeit lehnt ein nicht-primes p bewusst ab, statt stillschweigend einen falschen Rest zu liefern. Studierende, die den Satz im Olympiadenmaterial treffen, Entwickler, die Wettbewerbsbibliotheken anbinden, und Lehrende, die Labore zur modularen Arithmetik vorbereiten, profitieren von einer einzigen deterministischen Funktion, die die Primheitsannahme erzwingt und die in der Beweisführung genutzten Ziffernentwicklungen offenlegt.

Wie dieser Rechner den Satz von Lucas Schritt für Schritt anwendet

Rufen Sie die Fähigkeit mit den ganzzahligen Feldern n, k und p auf. Sowohl n als auch k müssen nichtnegative ganze Zahlen von höchstens einer Billion sein; p muss eine Primzahl zwischen zwei und einer Million drei einschließlich sein. Die Implementierung prüft zuerst Typen und Schranken und führt dann einen deterministischen Primheitstest durch Probedivision auf p aus.

Wenn p akzeptiert ist, durchläuft der Löser die Basis-p-Ziffern von n und k vom niedrigstwertigen zum höchstwertigen. Jedes kleine Binomial nutzt die multiplikative Formel mit modularen Inversen über den kleinen Satz von Fermat (a hoch p minus zwei modulo p), umgesetzt mit exakten BigInt-Zwischenprodukten, damit innerhalb der veröffentlichten Schranken keine Präzision verloren geht.

Randfälle sind stabil und dokumentiert: ist k null oder gleich n, ist das Ergebnis eins modulo p (oder null nur, wenn p eins wäre, was abgelehnt wird); übersteigt k n, ist das Ergebnis null; sind n und k beide null, sind die Ziffernarrays die einzelne Ziffer null und das Ergebnis ist eins modulo p.

Praktischer Einsatz, Grenzen, Preis und Auslieferung

Nutzen Sie das Browser-Werkzeug, wenn Sie beim Lesen einer zahlentheoretischen Notiz, beim Prüfen eines Wettbewerbsbeispiels oder beim Debuggen einer modular-kombinatorischen Routine eine schnelle Lucas-Prüfung wollen. Akzeptierte Eingaben sind nichtnegative ganze Zahlen n und k bis zu einer Billion sowie Primzahlen p von zwei bis einer Million drei. Binden Sie den Endpunkt in Olympiadenhilfen, Sandboxes der Wettbewerbsprogrammierung, kryptographische Lehrdemos zu Binomialkoeffizienten modulo kleiner Primzahlen oder jede Integer-Pipeline ein, die exakte modulare Arithmetik Näherungsbibliotheken vorzieht.

Wenn Sie den uneingeschränkten ganzen C(n, k), eine Binomialzeile für alle k oder modulare Binomiale für zusammengesetzte Moduln über den Chinesischen Restsatz brauchen, nutzen Sie eine eigene Fähigkeit; dieses Werkzeug bleibt bewusst bei Lucas für eine geprüfte Primzahl p, damit der Vertrag einfach und prüfbar bleibt.