In der Zahlentheorie stellt der Lehrsatz von Wilson fest, dass eine natürliche Zahl n> 1 eine Primzahl wenn und nur wenn ist

:

(sieh factorial und Modularithmetik für die Notation).

Geschichte

Der Lehrsatz war Ibn al-Haytham (auch bekannt als Alhazen) in um 1000 n.Chr. bekannt, aber es wird nach John Wilson (ein Student des englischen Mathematikers Edward Waring) genannt, wer es im 18. Jahrhundert festgesetzt hat. Waring hat den Lehrsatz 1770 bekannt gegeben, obwohl weder er noch Wilson es beweisen konnten. Lagrange hat den ersten Beweis 1771 gegeben. Es gibt Beweise, dass Leibniz auch des Ergebnisses ein Jahrhundert früher bewusst war, aber er hat es nie veröffentlicht.

Beweise

Beide der Beweise (für Hauptmodule) machen von der Tatsache Gebrauch, dass die Rückstand-Klassen modulo eine Primzahl ein Feld sind. Sieh den Artikel Hauptfeld für mehr Details. Der Lehrsatz von Lagrange (in jedem Feld, das ein Polynom des Grads n an den meisten N-Wurzeln hat) ist für beide Beweise erforderlich.

Zerlegbares Modul

Wenn n zerlegbar ist, ist es durch eine Primzahl q, wo teilbar. Wenn zu dann kongruent wären, würde ihm auch zu 1 (mod q) kongruent sein. Aber (n  1)! ≡ 0 (mod q).

Tatsächlich ist mehr wahr. Mit der alleinigen Ausnahme 4, wo 3! = 6 ≡ 2 (mod 4), wenn n dann (n  1) zerlegbar ist! ist zu 0 (mod n) kongruent. Der Beweis wird in zwei Fälle geteilt: Erstens, wenn n factored als das Produkt von zwei ungleichen Zahlen, wo 2  a sein kann

Hauptmodul

Das Ergebnis ist wenn trivial, so nehmen Sie an, dass p eine sonderbare Blüte ist. Da die Rückstand-Klassen (mod p) ein Feld sind, hat jede Nichtnull a ein einzigartiges multiplicative Gegenteil, a. Der Lehrsatz von Lagrange deutet an, dass die einzigen Werte, für den sind (weil die Kongruenz höchstens zwei Wurzeln (mod p) haben kann.) Deshalb, mit Ausnahme von ±1, können die Faktoren dessen in ungleichen Paaren eingeordnet werden, wo das Produkt jedes Paares ist. Das beweist den Lehrsatz von Wilson.

Zum Beispiel, wenn,

:

Hauptmodul - ein anderer Beweis

Wieder ist das Ergebnis für p = 2 trivial, so nehmen Sie an, dass p eine sonderbare Blüte ist. Denken Sie das Polynom

:

g hat Grad, Begriff und unveränderlichen Begriff führend. Seine Wurzeln sind 1, 2....

Denken Sie jetzt

:

h hat auch Grad und Begriff führend. Modulo p, der kleine Lehrsatz von Fermat sagt, dass es auch dieselben Wurzeln, 1, 2 hat....

Denken Sie schließlich

:

f hat Grad am grössten Teil von p  2 (da die Hauptbegriffe annullieren), und modulo p auch die Wurzeln 1, 2 hat.... Aber der Lehrsatz von Lagrange sagt, dass er mehr nicht haben kann als p  2 Wurzeln. Deshalb muss f (mod p), so sein unveränderlicher Begriff identisch Null-sein. Das ist der Lehrsatz von Wilson.

Anwendungen

Der Lehrsatz von Wilson ist als ein Primality-Test in der Praxis, seit der Computerwissenschaft (n  1) nutzlos! modulo n für großen n ist hart, und viel leichtere Primality-Tests sind bekannt (tatsächlich, sogar Probe-Abteilung ist beträchtlich effizienter).

Mit dem Lehrsatz von Wilson für jede sonderbare Blüte können wir die linke Seite von umordnen

:

die Gleichheit zu erhalten

:

Das wird

:

Wir können diese Tatsache verwenden, um einen Teil eines berühmten Ergebnisses zu beweisen: Für jeden ersten solchen p, dass p  1 (mod 4) die Nummer (1) ein Quadrat (quadratischer Rückstand) mod p ist. Dafür nehmen p = 4k + 1 für eine ganze Zahl k an. Dann können wir M = 2k oben nehmen, und wir schließen das

:

Der Lehrsatz von Wilson ist verwendet worden, um Formeln für die Blüte zu bauen, aber sie sind zu langsam, um praktischen Wert zu haben.

Die Generalisation von Gauss

Gauss hat dass wenn m> 2 bewiesen

:

\prod_ {k = 1 \atop \gcd (k, m) =1} ^ {M} \! \! k \\equiv

\begin {Fälle }\

- 1 \pmod {M} & \text {wenn} m=4, \; p^\\Alpha, \; 2p^\\Alpha \\

\; \; \, 1 \pmod {M} & \text {sonst}

\end {Fälle}

</Mathematik>

wo p eine sonderbare Blüte ist, und eine positive ganze Zahl ist. Die Werte der M, für die das Produkt 1 ist, sind genau diejenigen, wo es eine primitive Wurzel (mod m) gibt.

Das verallgemeinert weiter zur Tatsache, dass in jeder begrenzten abelian Gruppe entweder das Produkt aller Elemente die Identität ist, oder es genau ein Element vom Auftrag 2 (aber nicht beide) gibt. Im letzten Fall kommt das Produkt aller Elemente a gleich.

Siehe auch

• Primitive Wurzel modulo n
• Wilson erster
• Ibn_al-Haitham

Referenzen

Der Disquisitiones Arithmeticae ist aus dem Ciceronian Latein von Gauss ins Englisch und Deutsch übersetzt worden. Die deutsche Ausgabe schließt alle seine Papiere auf der Zahlentheorie ein: alle Beweise der quadratischen Reziprozität, der Entschluss vom Zeichen der Summe von Gauss, der Untersuchungen der biquadratic Reziprozität und unveröffentlichten Zeichen.

Links