Übrig blieb, zu beweisen, dass sqrt(a) irrational ist, wenn a keine Quadratzahl ist.
Indirekter Beweis:
(alle Zahlen a, p, q, x, y, z, k sind nichtnegative ganze Zahlen)
Angenommen sqrt(a) ist rational. Von allen mögliche Brüchen für sqrt(a) sei p/q jener mit kleinstem Wert für q (*). Natürlich ist q != 1, da sonst a Quadratzahl a = p^2 wäre.
---------
Hilfssatz:
Für das oben gewählte p und q existiert ein x aus [0, q) mit xp = 1 (mod q). (**)
Denn:
Es gibt maximal q verschiedene Reste für xp/q. Gäbe es den Rest 1 von oben nicht, dann hätten wir höchstens q-1 verschiedene Reste für q Werte x aus [0, q). D.h. mindestens ein Rest muss doppelt vorkommen. Also haben wir mindestens ein Paar y, z mit 0 <= y < z < q (***) mit dem gleichen Rest für yp/q und für zp/q also für das gilt yp = zp (mod q).
==> (z-y)p = kq
wegen (z-y) > 0 aus (***)
==> p/q = k/(z-y).
Wegen (*) folgt, dass z-y >= q ist und das ist ein Widerspruch zu (***).
Hilfssatz qed.
Bemerkung: Das ist nicht ganz der Chinesische Restsatz, denn der fordert, dass p und q teilerfremd sind und braucht zum Beweis die
Eindeutigkeit der Primfaktorzerlegung auf deren Benutzung wir ja verzichten wollten und auch verzichtet haben.
----------
Das Weitere ist leicht:
sqrt(a)=p/q
==> q^2 a = p^2
beide Seiten mit x^2 multiplizieren
==> x^2 q^2 a = x^2 p^2
Die Gleichung muss auch modulo q gelten
==> (x^2 q a) q = (xp)(xp) (mod q)
mit (**) auf der rechten Seite machen wir den Sack zu:
==> 0 = 1
Widerspruch und qed.
