wenn n keinen Primfaktor kleiner od. gleich √n hat, dann ist n eine Primzahl.
Beweis indirekt:
Annahme n hat einen Primfaktor k > √n
Dann gibt es ein m Element N so dass m*k = n |:k
m = n/k ist ein Faktor von n
Da k> √n
m= n/k < n/√n = √n
Also n ist durch m<√n teilbar. Die Primfaktorzerlegung von m enthält sicher einen Faktor kleiner als √n.
Das ist der gewünschte Widerspruch zur Annahme.
n muss somit eine Primzahl sein, wenn n keinen Primfaktor kleiner od. gleich √n hat,
