Bemerkung ueber die Aufloesung quadratischer Congruenzen.

Von Alberto Tonelli in Rom.

(Vorgelegt von Ernst Schering am 7. November.)

Auszug aus Briefen vom 18. April und 15. Juni 1891.

Das bekannte Verfahren zur allgemeinen Aufloesung einer quadratischen
Congruenz fuer einen Modul, welcher eine von der Form 4h+1 verschiedene
Primzahl ist, habe ich in der Weise verallgemeinert, dass es auch auf
Primzahlen dieser latzteren Form anwendbar wird.

Wenn die Congruenz

  xx = c (mod. p)

zur Aufloesung vergegeben ist und noch ein beliebiger quadratischer
Nichtrest g (mod. p) bekannt ist, so besteht dies Verfahren im
Folgenden.

Es sei p = a 2^s + 1, worin a ungerade s >= 1 ist, dann wird nach dem
Eulerschen Satze

  c^{a 2^{s-1}} = +1,  g^{a 2^{s-1} = -1 (mod. p).

Wenn noch s >= 2 ist, folgt aus der ersteren dieser beiden Congruenzen
die neue

  c^{a 2^{s-2}} = +-1 (mod. p).

Es sei nun e_0 = 0 wenn das obere (+)Zeichen, e_1 = 1 wenn das untere
(-)Zeichen stattfindet, so dass immer

  g^{e_0 a 2^{s-1}} c^{a 2^{s-2}} = +1 (mod. p)

wird. Wenn nun noch s >= 3 ist, so folgt hieraus

  g^{e_0 a 2^{s-2}} c^{a 2^{s-3}} = +- 1 (mod. p).

Gilt hier das obere (+) Zeichen, so setze ich e_1 = 0, gilt das unter
(-)Zeichen, so setze ich e_1 = 1, so dass immer

  g^{e_1 a 2^{s-1}} g^{e_0 a 2^{s-2}} c^{a 2^{s-3}} = +1 (mod. p)

wird. Auf diese Weise erhaelt man die Congruenz

  g^{a 2^{s-k}(e_0 + e_1 2 + ... + e_{k-1}2^{k-1})} c^{a 2^{s-k-1}} = 1 (mod. p)

so lange noch k < s ist; also fuer k = s - 1 wird

  g^{a 2(e_0 + e_1 2 + ... + e_{s-2}2^{s-2})} c^a = 1 (mod. p)

und demnach

  x = +- g^{a(e_0+e_1 2 + ... + e_{s-2}2^{s-2})} c^{(a+1)/2} (mod. p)

gesetzt, gibt die Wurzeln der Congruenz

  xx = c (mod. p).

Aus dieser Loesung erhaelt man durch

  x_1 = x^{p^{l-1}} c^{(p^l-2 p^{l-1}+1)/2}  (mod. p^l)

eine allgemeine Aufloesung der Congruenz

  x_1 x_1 = c (mod. p^l),

wie man sich leicht mit Anwendung des verallgemeinerten Fermatschen
Satzes und des Satzes ueberzeugt, dass wenn

  a = b (mod. p)   ist, auch   a^{p^{l-1}} = b^{p^{l-1}}  (mod. p^l)

wird.

Diese Formeln fuer die Wurzeln sind nicht nur theoretisch
bemerkenswerth, sondern sie koennen auch in Faellen, wo andere besondere
Methoden ihren Dienst versagen, von praktischer Bedeutung zur Berechnung
der Wurzel der quadratischen Congruenzen sein.