Wir gehen weiter zu einem Satz aus der Zahlentheorie.
V Für eine zusammengesetzte Zahl n=a·b (a, b ε N, a ≤ b) gilt: a2≤ n
Will man zum Beispiel prüfen ob 401 eine zusammengesetzte Zahl ist (also
keine Primzahl), genügt es zu testen, ob eine der Zahlen von 2 bis 20 Teiler von 401 ist, es genügt sogar zu prüfen, ob eine der Primzahlen 2,3,5,7,11,13,17 oder 19 Teiler von 401 ist. (Dies ist nicht der Fall: also ist 401 Primzahl.)
Beachte zum Beweis, dass a
2 ≤ n gleichbedeutend ist mit a ≤ √
n (a, n ε
N).
Zeige, dass es für a·b = n unmöglich ist dass sowohl a > √
n als auch b > √
n ist.
Lösung