Primzahlen: Ib. Kapitel: Variationen zur Teilbarkeit von Primzahlen

Primzahlen

Wie im Vorwort schon erwähnt, lässt sich eine Primzahl als eine natürliche Zahl größer 1, die nur durch 1 und sich selbst teilbar ist, definieren. Aufgrund dieser Eigenschaft existiert der naive Primzahlentest, bei der eine Zahl $n$ auf die Teilbarkeit durch alle Zahlen zwischen 2 und ${\sqrt {n}}$ getestet wird:

Eine Primzahl: 7 $7\mod 2=1$ : teilerfremd! $7\mod 3=1$ : teilerfremd! $7\mod 4=3$ : teilerfremd! $7\mod 5=2$ : teilerfremd! $7\mod 6=1$ : teilerfremd!

Keine Primzahl: 12 $12\mod 2=0$ : nicht teilerfremd! $12\mod 3=0$ : nicht teilerfremd! $12\mod 4=0$ : nicht teilerfremd! $12\mod 5=2$ : teilerfremd! $12\mod 6=0$ : nicht teilerfremd!

In Zusammenhang mit der oben angegebenen Eigenschaft "Eine Primzahl als eine natürliche Zahl größer 1, die nur durch 1 und sich selbst teilbar ist" gibt es noch weitere Eigenschaften, die sich aus dieser Eigenschaft ableiten lassen:

1. Zwei natürliche Zahlen, deren Summe eine Primzahl ergeben, sind immer teilerfremd. Allerdings ergibt die Summe zweier teilerfremder natürlicher Zahlen nicht immer eine Primzahl.

Eine Primzahl: 11 $11=2+9$ : teilerfremd! $11=3+8$ : teilerfremd! $11=4+7$ : teilerfremd! $11=5+6$ : teilerfremd!

Keine Primzahl: 15 $15=2+13$ : teilerfremd! $15=3+12$ : nicht teilerfremd! $15=4+11$ : teilerfremd! $15=5+10$ : nicht teilerfremd! $15=6+9$ : nicht teilerfremd! $15=7+8$ : teilerfremd!

2. Es ist nicht möglich, eine Primzahl in die Form eines Rechtecks zu bringen.
Beispiele:

--1--2---3----4---5----6----7----8----9----10-----11----11---
--X--XX--XXX--XX--XXX--XXX-XXXX-XXXX--XXX--XXXXX--XXXX--XXXXX
--------------XX--XX---XXX-XXX--XXXX--XXX--XXXXX--XXXX--XXXXX
--------------------------------------XXX---------XXX---X----