Ich denke, daß die Lösung jetzt funktioniert: Gegeben ist eine ganze Zahl . Gesucht eine Zahl mit . Wegen des chinesischen Restesatzes kann man n in Primzahlpotenzen faktorisieren und für jede Primzahlpotenz separat die Betrachtung machen. O.B.d.A. kann man also annehmen, daß eine Primzahlpotenz ist. Wenn ist, dann ist bereits die Lösung und wir sind fertig, diesen Fall können wir also ausschließen. Wenn also nur , dann kann man eine gerade Potenz von p aus a herausziehen, deren Quadratwurzel zu ziehen trivial ist. Wenn danach immer noch gilt, dann läßt sich keine Quadratwurzel modulo n ziehen, denn wenn eine solche wäre, dann wäre , also nach der Definition einer Primzahl einer der beiden Faktoren des durch teilbaren Produkts durch teilbar, also , also , was ein Widerspruch ist. Für , in dem eine ungerade Potenz von steckt, gibt es also keine Quadratwurzel modulo n. Wir können jetzt annehmen, daß ist. (Das gilt übrigens alles auch für .) Für kann mit dem quadratischen-Reste-Symbol geprüft werden, ob es eine Lösung mit gibt. Genau dann läßt sich die Quadratwurzel modulo n ermitteln. Nun muß man eine Lösung finden, die modulo p stimmt. Sei (Vereinfachung der Schreibweise im folgenden): Nun wiederholt man solange, bis . Da und und teilerfremd zu sind, kann die Division modulo Dann ist eine Lösung. Dafür muß man (z.B. durch vollständige Induktion) beweisen, daß gilt. Für gilt das, denn wir haben so gewählt. Wenn es für ein beliebiges gilt, dann ist also für eine gemäß Hensel-Lemma vorhandene Lösung mit für ein das beliebig groß, also größer als ist, für ein ganzzahliges . Nun gilt , wobei gemäß der dritten binomischen Formel erweitert wurde. Nun gilt aber und und damit q.e.d. Für hat man die Situation, daß für alle . Damit ist für bereits die Lösung. Für höhere 2er-Potenzen muß man und eine Lösung mit finden. Hier verläuft der Beweis analog, man muß aber die anders wählen, weil die Division durch jeweils die 2er-Potenz, modulo der die Kongruenz gilt, um eins niedriger ausfallen läßt, aber wir mit beginnen: Wenn niemand etwas dagegen hat, würde ich vorschlagen, das sinngemäß so in den Artikel zu übernehmen. -- Karl Brodowsky 20:46, 25. Jan. 2012 (CET)