Teilbarkeit
Sind m <> 0 und n ganze Zahlen, so nennt man n durch m teilbar (in Zeichen: "m | n" für "m teilt n"), wenn es genau eine ganze Zahl q gibt mit n = m q. Für die Teilbarkeit gelten folgende Rechenregeln:
(1) Für jedes n <> 0 gilt n | 0 und n | n.
(2) Gilt m | n, dann auch -m | n und m | -n.
(3) Für alle n gilt 1 | n.
(4) Aus m | n und n <> 0 folgt |m| < |n|.
(5) Aus n | 1 folgt entweder n = 1 oder n = -1.
(6) Aus m | n und n | m folgt entweder m = n oder n = -m.
(7) Aus p | m und m | n folgt p | n.
(8) Wenn p <> 0, dann sind m | n und pm | pn gleichbedeutend.
(9) Gelten m | n1 und m | n2, dann folgt m | (p1n1 + p2n2) mit beliebigen p1, p2.
(10) Gelten m1 | n1 und m2 | n2, dann folgt m1m2 | n1n2.
(11) Ist p >= 2, so sind die Aussagen "p ist eine Primzahl" und "Aus p | n1n2 folgt p | n1 oder p | n2" äquivalent.
Aus (6) folgt, dass die Relation | auf der Menge N/{0} (natürliche Zahlen ohne Null) antisymmetrisch ist,
aus (7) folgt, dass sie transitiv ist und aus (1) folgt, dass sie reflexiv ist. Auf der angegebenen Grundmenge handelt es sich bei der Relation | also um eine reflexive Ordnungsrelation.
Ganze Zahlen n >= 2 mit genau zwei positiven Teilern heißen Primzahlen. Alle anderen Zahlen heissen zusammengesetzt. Ist n eine Primzahl so sind die einzigen Teiler 1 und n. Es gibt unendlich viele Primzahlen (Satz von Euklid).
Jede natürliche Zahl grösser Eins kann durch ein Produkt von Primzahlen dargestellt werden. Ordnet man die Faktoren des Produkts nach der Grösse, ist die Darstellung eindeutig (Fundamentalsatz der Arithmetik). Das Finden dieser Darstellung zu einer gegebenen Zahl nennt man Faktorisieren.