6. Erhalt der Teilbarkeit unter Linearkombinationen

Wir hatten die Division mit Rest verwendet, um zu argumentieren, dass jeder Primteiler p von a = p₁ … p_n + 1 von p₁, …, p_n verschieden ist. Die Division mit Rest lässt sich aufgrund der Konstruktion von a direkt ablesen. So ist zum Beispiel

a = (p₂ … p_n) p₁ + 1

die Division mit Rest der Zahl a durch p₁. Es ist auch anschaulich klar, dass der direkte Nachfolger eines Vielfachen einer Zahl d ≥ 2 kein Vielfaches von d ist und damit nicht durch d teilbar sein kann. Das nächstgrößere Vielfache erhalten wir durch Addition von d. Die Vielfachen von d sind

d, 2d, 3d, 4d, 5d, …, nd, (n + 1)d, …

Genau die Zahlen, die nicht in dieser Folge vorkommen, sind nicht durch d teilbar. Die Folge hat eine Schrittweite d > 1, sodass direkte Nachfolger nicht vorkommen. Sie werden übersprungen.

Es ist instruktiv, das Argument noch etwas anders zu führen. Wir zeigen hierzu einen allgemeinen Satz, den wir im größeren Rahmen der ganzen Zahlen formulieren:

Satz (Erhalt gemeinsamer Teiler bei Addition und Subtraktion)

Seien d, n, m ganze Zahlen, und sei d ein gemeinsamer Teiler von n und m. Dann ist d ein Teiler von n + m und n − m.

Beweis

Nach Voraussetzung gibt es ganze Zahlen k₁ und k₂ mit n = k₁ d und m = k₂ d. Dann gilt aufgrund des Distributivgesetzes

n + m = k₁ d + k₂ d = (k₁ + k₂) d.

Dies zeigt, dass d ein Teiler von n + m ist. Analoges gilt für n − m.

Damit erhalten wir unser obiges Ergebnis als Geschenk:

Korollar (Teilerfremdheit aufeinanderfolgender Zahlen)

Sei n ≥ 1 eine natürliche Zahl. Dann sind n und n + 1 teilerfremd.

Beweis

Sei d ≥ 1 ein gemeinsamer Teiler von n und n + 1 Nach dem Satz ist d ein Teiler von (n + 1) − n = 1. Folglich ist d = 1.

Wie oben folgt nun die Unendlichkeit der Primzahlen. Eine Division mit Rest muss nicht verwendet werden.

Unser Satz lässt sich noch weiter verallgemeinern. Die folgende Version wird in der Zahlentheorie sehr häufig verwendet:

Satz (Erhalt gemeinsamer Teiler bei Linearkombination)

Seien d, n, m ganze Zahlen, und sei d ein gemeinsamer Teiler von n und m. Weiter seien λ, μ ganze Zahlen. Dann ist d ein Teiler von λn + μm.

Der Beweis wird erneut durch Anwendung des Distributivgesetzes geführt (der Leser führe das Argument explizit durch). Im Fall λ = 1 und μ = ±1 erhalten wir den Erhaltungssatz für die Addition und Subtraktion.

Beispiel

Seien n = 2 · 3 = 6, m = 3 · 5 = 15 und d = 3. Dann ist d ein Teiler von n und m. Gleiches gilt für die folgenden ganzzahligen Linearkombinationen von n und m:

1 · 6 + 1 · 15 = 21

1 · 6 − 1 · 15 = −9

(−1) · 6 + 1 · 15 = 9

2 · 6 + 4 · 15 = 72

5 · 6 − 2 · 15 = 0

8 · 6 − 3 · 15 = 3