Die Elemente der Zahlentheorie / dargestellt von Paul Bachmann.

110 Dritter Abschnitt
1) Zunächst sei m == p, unter p eine ungerade Primzahl
verstanden. Ist nun die Congruenz
(10) x2 - n (mod. p1")
möglich, so sei a eine Wurzel derselben, also
a2 _ n (mod. ps1)
oder
a2 - n - hpt.
Setzen wir dann
x -= a- + - y,
folglich
x2 -n = a2 - n + 2ay - p1." + 2 p. p2
und
2 - n - (2 cy + h). p" (mod. p+ ),
so wird offenbar x2 - n theilbar durch p+l1, wenn y so gewählt wird, dass 2ay + h _ O (mod.p) wird. Das ist aber
stets möglich; denn da n relativ prim zum Modulus, d. i. zu
p vorausgesetzt wird, so ist es auch a und ebenso 2a, die Congruenz ersten Grades kann also gelöst werden. Hieraus folgt:
die Möglichkeit der Congruenz (10) reicht hin, auch die der
Congruenz
x2- n (mod. p'l)
zu sichern. Und da diese Betrachtung unabhängig ist vom
Werthe des Exponenten t, so schliesst man: Zur Möglichkeit
der Congruenz (10) ist die der einfacheren Congruenz (4) ausreichend; offenbar aber auch nothwendig, weil aus der Congruenz (10) a fortiori auch die Congruenz (4) hervorgeht.
Also: Zur Möglichkeit der Congruenz (10) ist nothwendig und hinreichend, dass n ein quadratischer
Rest sei von p. In diesem Falle hat die Congruenz
genau 2 Wurzeln. Denn, ist a eine Lösung derselben, x
irgend eine andere, so findet sich aus den Congruenzen
x2-n, ~a2 = n (mod. pj)
die folgende:
(x - a) (x + a) - 0 (mod. p").
Nun sind x und a, desgleichen, da p ungerade ist, auch 2x
und 2a relativ prim zu p. Diese Zahlen sind aber Summe
und Differenz jener beiden Faktoren, deren Produkt durch pt