Teilbarkeit und Teilbarkeitsregeln

Für die Erkennung von Primzahlen ist die Erkennung von Teilbarkeit durch andere Zahlen als die 1 und die Zahl selbst sehr wichtig.
Mit einigen wenigen Regeln lassen sich auf diese Art bei vielen Zahlen schon ausschließen, daß es sich um Primzahlen handelt.

Was ist Teilbarkeit?

Eine Zahl a heißt durch eine andere Zahl b teilbar, wenn bei der Division der ersten Zahl durch die zweite Zahl (a:b) kein ganzzahliger Rest bleibt, d.h. wenn die Division keine Nachkommastellen ergibt.

Teilbarkeitsregeln

Sobald eine Zahl durch eine andere Zahl als die 1 oder sich selbst teilbar ist, ist sie keine Primzahl.
Mit den folgenden einfachen Regeln, kann die Primzahleigenschaft für viele Zahlen schon ausgeschlossen werden:

  • Eine Zahl ist durch 2 teilbar, wenn sie gerade ist, d.h. die Endziffer 2,4,6,8 oder 0 ist.
  • Eine Zahl ist durch 3 teilbar, wenn auch ihre Quersumme durch 3 teilbar ist.
  • Eine Zahl ist durch 4 teilbar, wenn die beiden Endziffern durch 4 teilbar sind.
  • Eine Zahl ist durch 5 teilbar, wenn die Endziffer eine 5 oder eine 0 ist.
  • Eine Zahl ist durch 9 teilbar, wenn ihre Quersumme durch 9 teilbar ist.

Es gibt weitere Regeln für Teilbarkeit, die sind aber deutlich komplexer: