Divisibilität

Die Divisibilität ist der eigentliche Ausgangspunkt der Zahlentheorie, weil sie die ganzen Zahlen in ein System mit Struktur verwandelt: Man betrachtet Zahlen nicht mehr als bloße „Mengen“, sondern als Elemente, die zueinander passen oder nicht passen. Mit einer einzigen Struktur, a\mid b, lassen sich sowohl Kriterien der Vereinfachung und Faktorisierung als auch der Kern einiger Verfahren ausdrücken, etwa des euklidischen Algorithmus, der es ermöglicht, größte gemeinsame Teiler selbst bei großen Zahlen in Sekunden zu berechnen. Darüber hinaus bildet sie die technische Grundlage von Ideen, die in der angewandten Mathematik und der Informatik immer wieder auftreten: Kongruenzen, modulare Arithmetik, Validierungen, Codes und (in weiterer Folge) Kryptographie. Die Beherrschung der Divisibilität bedeutet im Wesentlichen, unsichtbare Muster in den ganzen Zahlen zu erkennen und sie in Verfahren zu überführen, die stets funktionieren.

Lernziele
Am Ende dieses Skripts wird der Studierende in der Lage sein:

1. die Teilbarkeitsrelation zwischen ganzen Zahlen zu verstehen.
2. die Definition der Divisibilität und ihre Eigenschaften zu verstehen.
3. mathematische Beweise von Ergebnissen und Theoremen im Zusammenhang mit der Divisibilität zu entwickeln.

INHALTSVERZEICHNIS
Definition der Divisibilität
Grundlegende Eigenschaften der Divisibilität
Vorgeschlagene Übungen

Definition der Divisibilität

Die informelle Idee von „a teilt b“ wird präzise, wenn wir sie als eine Relation zwischen ganzen Zahlen ausdrücken. Wir sagen, dass eine ganze Zahl a eine ganze Zahl b teilt, wenn b als ein exaktes Vielfaches von a geschrieben werden kann. Diese Definition bildet die Grundlage des gesamten Skripts, da sie Aussagen der Art „passt genau“ in ein überprüfbares Kriterium überführt.

Definition. Seien a,b\in\mathbb{Z} mit a\neq 0. Wir sagen, dass a b teilt, und schreiben a\mid b, genau dann, wenn es eine ganze Zahl k\in\mathbb{Z} gibt, sodass b=ka. Andernfalls schreiben wir a\nmid b.

a\mid b := (\exists k \in \mathbb{Z})(b = ka )

In dieser Definition wird die Zahl k als Quotient (oder Faktor) bezeichnet, der mit der Divisibilität verknüpft ist. Beispielsweise ist die Aussage 6\mid 42 gleichbedeutend mit der Behauptung, dass es ein k\in\mathbb{Z} gibt, sodass 42=6k; in diesem Fall genügt es, k=7 zu wählen.

Es ist wichtig zu berücksichtigen

• Die Bedingung a\neq 0 ist wesentlich. Würde man versuchen, a=0 zuzulassen, so würde die Teilbarkeitsbedingung verlangen, dass es ein k\in\mathbb{Z} gibt, sodass b=0\cdot k gilt. Da jedoch 0\cdot k=0 für jedes k ist, wäre die einzige Möglichkeit b=0. In diesem Fall gäbe es kein durch die Relation „festgelegtes“ k, da jedes k\in\mathbb{Z} die Gleichung 0=0\cdot k erfüllt. Anders ausgedrückt wird der informelle Ausdruck k=b/a zu k=0/0, was nicht definiert ist. Um diese Degeneration zu vermeiden, bei der der Begriff des Quotienten seine Bedeutung verliert, fordert man a\neq 0. Aus diesem Grund wird die Relation 0\mid b nicht als gültig betrachtet.
• Dagegen ist a\mid 0 für jedes a\in\mathbb{Z} mit a\neq 0 wahr, da es genügt, k=0 zu wählen, und dann 0=a\cdot 0 gilt.

Aus dieser Definition folgt eine Äquivalenz, die wir wiederholt verwenden werden: Zu sagen, dass a\mid b gilt, ist gleichbedeutend damit, dass b zur Menge der ganzzahligen Vielfachen von a gehört, das heißt b\in a\mathbb{Z}, wobei a\mathbb{Z}=\{ak:\,k\in\mathbb{Z}\} ist. Diese Schreibweise hebt hervor, dass die Divisibilität kein „Trick“ ist, sondern eine Art, sehr strukturierte Teilmengen innerhalb von \mathbb{Z} zu beschreiben.

Grundlegende Eigenschaften der Divisibilität

• Reflexivität: a\mid a.
  Beweis:

  \begin{array}{rll} (1)&\vdash a=ka \leftrightarrow k=1 &\text{; Multiplikatives Neutralelement in $\mathbb{Z}$}\\ (2)&\vdash(\exists k \in \mathbb{Z})(a=ka) &\text{; Existentielle Einführung (1)}\\ (3) &\vdash a \mid a &\text{; Def. der Divisibilität (2)} \\ &\blacksquare & \end{array}

• Transitivität: wenn a\mid b und b\mid c, dann a\mid c.

  Beweis:

  \begin{array}{rll} (1)& \{a\mid b , b\mid c\} \vdash (\exists k_1\in\mathbb{Z})(b=k_1a) &\text{; Def. der Divisibilität, Voraussetzung}\\ (2)& \{a\mid b , b\mid c\} \vdash (\exists k_2\in\mathbb{Z})(c=k_2b) &\text{; Def. der Divisibilität, Voraussetzung}\\ (3)& \{a\mid b , b\mid c\} \vdash (\exists k_1,k_2\in\mathbb{Z})(b=k_1a \wedge c=k_2b) &\text{; $\exists$-Kompaktierung(1,2)}\\ (4)& \{a\mid b , b\mid c\} \vdash (\exists k_1,k_2\in\mathbb{Z})(k_2b=k_1k_2a \wedge c=k_2b) &\text{; Aus(3)}\\ (5)& \{a\mid b , b\mid c\} \vdash (\exists k_1,k_2\in\mathbb{Z})( c=k_1k_2a) &\text{; Aus(4)}\\ &\text{Algebra innerhalb des Quantors}& \\ (6)& \{a\mid b , b\mid c\} \vdash (\exists k\in\mathbb{Z})( c=ka) &\text{; Aus(5)}\\ &\text{Abgeschlossenheit von $\mathbb{Z}$ unter der Multiplikation}& \\ (7)& \{a\mid b , b\mid c\} \vdash a\mid c &\text{; Def. der Divisibilität (6)}\\ (8)& \vdash (a\mid b \wedge b\mid c) \rightarrow a\mid c &\text{; $\wedge$-TD(7)}\\ &\blacksquare& \end{array}

• Verträglichkeit mit Addition und Subtraktion: wenn a\mid b und a\mid c, dann a\mid (b+c) und a\mid (b-c).
  Beweis:

  \begin{array}{rll} (1)&\{a\mid b, a\mid c\}\vdash (\exists k_1 \in \mathbb{Z})(b=k_1 a) &\text{; Def. der Divisibilität, Voraussetzung}\\ (2)&\{a\mid b, a\mid c\}\vdash (\exists k_2 \in \mathbb{Z})(c=k_2 a) &\text{; Def. der Divisibilität, Voraussetzung}\\ (3)&\{a\mid b, a\mid c\}\vdash (\exists k_1, k_2 \in \mathbb{Z})(b=k_1 a \wedge c=k_2 a) &\text{; $\exists$-Kompaktierung(1,2)}\\ (4)&\{a\mid b, a\mid c\}\vdash (\exists k_1, k_2 \in \mathbb{Z})(b+c= (k_1+k_2)a) &\text{; Aus(3)}\\ &\text{Algebra innerhalb des Quantors.}& \\ (5)&\{a\mid b, a\mid c\}\vdash (\exists k \in \mathbb{Z})(b+c= ka) &\text{; Aus(4)}\\ &\text{Abgeschlossenheit von $\mathbb{Z}$ unter der Addition.}& \\ (6)&\{a\mid b, a\mid c\}\vdash a\mid (b+c) &\text{; Def. der Divisibilität (5)}\\ (7)&\vdash (a\mid b \wedge a\mid c) \rightarrow a\mid (b+c) &\text{; $\wedge$-TD(6)}\\ (8)&\{a\mid b, a\mid c\}\vdash (\exists k_1, k_2 \in \mathbb{Z})(b-c= (k_1-k_2)a) &\text{; Aus(3)}\\ &\text{Algebra innerhalb des Quantors.}& \\ (9)&\{a\mid b, a\mid c\}\vdash (\exists \overline{k} \in \mathbb{Z})(b-c= \overline{k}a) &\text{; Aus(8)}\\ &\text{Abgeschlossenheit von $\mathbb{Z}$ unter der Subtraktion.}& \\ (10)&\{a\mid b, a\mid c\}\vdash a\mid (b-c) &\text{; Def. der Divisibilität (9)}\\ (11)&\vdash (a\mid b \wedge a\mid c) \rightarrow a\mid (b-c) &\text{; $\wedge$-TD(10)}\\ (12)&\vdash (a\mid b \wedge a\mid c) \rightarrow \left(a\mid (b+c) \wedge a\mid (b-c)\right) &\text{;$\wedge$-Einführung im Konsequens(7,11) }\\ &\blacksquare& \end{array}

• Verträglichkeit mit Produkten: wenn a\mid b, dann a\mid (bc) für jedes c\in\mathbb{Z}.
  Beweis:

  \begin{array}{rll} (1)& \{a\mid b\}\vdash (\exists k\in\mathbb{Z})(b=ka) &\text{; Def. der Divisibilität, Voraussetzung}\\ (2)& \{a\mid b\}\vdash \left(\forall c \in \mathbb{Z}\right) (\exists k\in\mathbb{Z})(cb=cka) &\text{; Aus(1), $\forall$-Einführung (c beliebig)}\\ &\text{Algebra in }\mathbb{Z}\text{ innerhalb des existenziellen Quantors.}&\\ (3)& \{a\mid b\}\vdash \left(\forall c \in \mathbb{Z}\right) (\exists \overline{k}\in\mathbb{Z})(cb=\overline{k}a) &\text{; Aus(2), Abgeschlossenheit: }\overline{k}=ck\\ (4)& \{a\mid b\}\vdash \left(\forall c \in \mathbb{Z}\right) (a \mid cb) &\text{; Def. der Divisibilität (3)}\\ (5)& \vdash a\mid b \rightarrow \left(\forall c \in \mathbb{Z}\right) (a \mid cb) &\text{; TD(4)}\\ &\blacksquare& \end{array}

Satz: Schranke des Teilers

Ist b\neq 0 und a\mid b, so gilt |a|\le |b|.

Beweis:

\begin{array}{rll} (1) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash b \neq 0 & \text{; Voraussetzung} \\ (2) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (b=ka) & \text{; Def. der Divisibilität, Voraussetzung} \\ (3) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (|b|=|k||a|) & \text{; Eigenschaft des Absolutbetrags, aus (2)} \\ (4) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (k\neq 0 \wedge |b|=|k||a|) & \text{; Aus (1,3)} \\ (5) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash (\exists k \in \mathbb{Z}) (1\le |k| \wedge |b|=|k||a|) & \text{; Aus (4), denn }k\neq 0\Rightarrow |k|\ge 1 \\ (6) &\{b\in \mathbb{Z}\setminus\{0\} , a\mid b\}\vdash |a|\le |b| & \text{; Aus (5)} \\ &\blacksquare& \end{array}

Vorgeschlagene Übungen

1. Zeigen Sie, dass der Satz „Schranke des Teilers“ nicht notwendigerweise gilt, wenn b=0.
2. Betrachten wir eine Menge A und eine Relation \rho auf dieser Menge. Sind die Elemente x,y\in A so beschaffen, dass x mit y durch \rho in Relation steht, so schreibt man x\rho y. Die Relation \rho heißt eine partielle Ordnungsrelation auf A, wenn gilt:

   a)(\forall x\in A) (x\rho x),
   b) (\forall x,y\in A) ( (x\rho y \wedge y\rho x) \rightarrow x=y)
   c) (\forall x,y,z\in A) ( (x\rho y \wedge y\rho z) \rightarrow x\rho z).

   Beweisen Sie, dass die Teilbarkeitsrelation eine partielle Ordnungsrelation auf den ganzen Zahlen ist.

3. Beweisen Sie mittels Induktion, dass aus a\mid b_1, a\mid b_2, \cdots, a\mid b_n folgt, dass a\mid \sum_{i=1}^n b_i x_i für jede Menge \{x_i\}_{i=1}^n \subset \mathbb{Z}. Beweisen Sie außerdem, dass, wenn a\mid b_i mit i\in \{1,2,3,\cdots, n\} gilt und c als eine lineare Kombination dieser b_i geschrieben werden kann, dann a\mid c gilt.
4. Ist a\neq 0, so zeigen Sie, dass die Menge \{x\;:\; d\mid a\} endlich ist.
5. Betrachten Sie ein festes n\in\mathbb{Z}^+, und sei

   S=\{d\,:\,d\in\mathbb{Z}^+ \wedge d\mid n\}

   Beweisen Sie:

   1. d\in S \leftrightarrow n/d\in S
   2. Werden die Elemente von S in aufsteigender Reihenfolge angeordnet: 1=d_1 \lt d_2 \lt \cdots \lt d_t =n, so stehen die zugehörigen Elemente n\mid d_i mit i \in \{1,2,\cdots, t\} in absteigender Reihenfolge.
6. Seien a,b\in\mathbb{Z}^+ und ab=c. Beweisen Sie, dass \min\{a,b\}\le \sqrt{c} gilt.
7. Eine ganze Zahl n heißt gerade, wenn 2\mid n, und ungerade, wenn 2\nmid n. Beweisen Sie, dass die Summe und die Differenz von:
   1. zwei geraden Zahlen eine gerade Zahl ist.
   2. zwei ungeraden Zahlen eine gerade Zahl ist.
   3. einer geraden und einer ungeraden Zahl eine ungerade Zahl ist.
8. Ist n eine ungerade Zahl verschieden von \pm 1, so zeigen Sie, dass n nicht zwei aufeinanderfolgende gerade Zahlen teilen kann.
9. Seien a,b,n\in\mathbb{Z} so, dass |a-b|\lt |n| gilt. Beweisen Sie, dass n weder a noch b teilen kann.
10. Sei a\in\mathbb{Z}. Beweisen Sie:
    1. (\forall n \in \mathbb{Z})(a\mid n) \leftrightarrow a=\pm 1
    2. (\forall n \in \mathbb{Z})(n\mid a) \leftrightarrow a=0
11. Seien a,b,c\in\mathbb{Z} und nehmen wir an, dass c\neq 0. Zeigen Sie, dass aus ac\mid bc folgt, dass a\mid b gilt.