Teilbarkeit

Aufgaben

1. Finde Beweise zu den Eigenschaften oben, zu denen keine Beweise angegeben sind.
2. Wenn $a\mid b$ gilt, dann gilt auch $a\mid b^2$
   Beweis
   $a\mid b\Rightarrow ax=b$
   $\phantom{a\mid b}\Rightarrow (ax)^2= b^2$
   $\phantom{a\mid b}\Rightarrow a(ax^2)= b^2$
   $\phantom{a\mid b}\Rightarrow a\mid b^2$
   
3. Für zwei ganze Zahlen $a$ und $b$ mit $b\gt a$ gilt: teilt $c$ sowohl $a$ als auch $b$, dann teilt $c$ auch $b-a$.
   Beweise dies.
   Beweis
   aus $c\mid b \wedge c\mid a$
   $\Rightarrow cx=b \wedge cy=a$
   $\Rightarrow b-a = (\underbrace{cx-cy}_{\gt 0})$
   $\Rightarrow b-a = c(x-y)$
   $\Rightarrow c\mid (b-a)$
4. Sei $p$ eine ungerade Zahl, dann gilt: $8\mid (p^2 - 1)$.
   Hinweise
   Hinweise:

   • Wir können zeigen dass es durch 8 teilbar ist oder
   • wir können zeigen dass es dreimal durch 2 teilbar ist, da $8=2\cdot 2\cdot 2$ ist oder
   • wir können zeigen dass es durch 4 teilbar ist und der Rest durch 2 teilbar ist, da $8=4\cdot 2$
   • Beginnen sollte man immer mit dem Einsetzen der Definition (hier für ungerade Zahlen)
   • Eine Zahl $k$ ist ungerade, wenn $k=2n+1$ ist oder alternativ $k=2n-1$

   
   Beweis

   Zu zeigen: $p^2-1$ ist durch 8 teilbar, für ungerade $p$
   Sei $p=2k+1$ mit $k\in\mathbb{Z}$, dann ergibt sich durch einsetzen:
   

   • $(2k+1)^2-1 = (2k)^2+2(2k)+1-1 = 4k^2+4k$
   • $4k^2+4k=4k(k+1)$ dies ist durch 4 teilbar
   • Wir müssen jetzt noch zeigen $k(k+1)$ durch 2 teilbar ist
   • Die Faktoren $k$ und $k+1$ sind zwei aufeinanderfolgende Zahlen
   • von zwei aufeinanderfolgenden Zahlen ist immer eine durch 2 teilbar, somit ist die Aussage wahr.
5. Zeige, dass wenn $3\not\mid n^2$ gilt, auch $3\not\mid n$ gilt.
   Beweis
   indirekter Beweis: $\neg(3\not\mid n)$ ist $3\mid n$.
   Aus $3\mid n$ folgt nach Definition $3k = n$ für ein $k\in\mathbb Z$.
   Quadriert man beide Seiten erhält man $3^2k^2=n^2$.
   Da $3(3k^2)$ durch 3 teilbar ist, ist $n^2$ durch 3 teilbar.
   Es gilt also $3\mid n^2$, was $\neg(3\not\mid n^2)$ entspricht.
6. Wenn $n \in\mathbb Z$, dann $4\not\mid (n^2 -3)$.
   Beweis
   Fall 1:

   $n$ ist gerade (sei $2k=n$), dann ist $n^2-3 = (2k)^2-3$ $= 4k^2-3$ $= 2b-1$ mit $b=2k^2$ ungerade.
   Eine ungerade Zahl ist nicht durch 4 teilbar

   Fall 2:

   $n$ ist ungerade (sei $2k+1=n$), dann ist $n^2-3 = (2k+1)^2-3$ $= 4k^2+4k+1-3$ $= 2(2k^2+2k-1)$
   Der zweite Faktor ist eine ungerade Zahl, denn: $2(2k^2+2k-1) = 2(\underbrace{2(k^2+k)-1}_{\text{ungerade}})$
   Somit ist $n^2-3$ für ungerade $n$ durch 2 aber nicht durch 4 teilbar. Denn der zweite Faktor ist eine ungerade Zahl, welche nicht durch 2 teilbar ist.
7. Mit dem Satz aus voriger Aufgabe kann man einen Algorithmus für den größten gemeinsamen Teiler ableiten.
   Der größte gemeinsame Teiler von $a$ und $b$ ist $ggT(a,b)$, ist von allen Zahlen, die sowohl $a$ als auch $b$ teilen, die größte.
   $ggT(a,b)=\left\{ \begin{array}{ll} a &\text{ falls } a=b\\ ggT(a-b, b) &\text{ falls } a\gt b\\ ggT(a,b-a) &\text{ falls } a\lt b\\ \end{array} \right.$
   Probieren Sie den Algorithmus mit $a=30$ und $b=42$ aus.
   Zeigen sie:
   teilt $c$ die Zahl $b-a$ und $c$ teilt $b$ mit $b\gt a$, so teilt $c$ auch $a$
   Warum muss dies gelten, dass der $ggT$-Algorithmus richtig arbeitet.
   Sei $\mathbb{M}$ die Menge der gemeinsamen Teiler von $a$ und $b$.
   Wie verändert sich diese Menge durch den $ggT$-Algorithmus?
   Bedenke, dass gilt:
   $c\mid a \wedge c\mid b \Rightarrow c\mid (b-a)$ und
   $c\mid (b-a) \wedge c\mid b \Rightarrow c\mid a$
   Beweis
   $ggT(30,42)=ggT(30,12) $ $= ggT(18, 12)$ $= ggT(6,12)$ $= ggT(6,6)=6$

   teilt $c$ die Zahl $b-a$ mit $b\gt a$, so teilt $c$ sowohl $a$ als auch $b$. Wenn $c\mid b-a \wedge c\mid b$
   $\Rightarrow cx = b-a \wedge cy = b$
   $\Rightarrow cy-cx = b-(b-a) $
   $\Rightarrow c(y-x) = a $
   $\Rightarrow c \mid a $
   

   Die Menge der gemeinsamen Teiler von $a$ und $b$ muss im Verlauf des Algorithmus gleich bleiben.
   Es darf kein Teiler "verschwinden" und
   es darf kein Teiler hinzukommen. (Überlegen sie, was wäre wenn dass nicht der Fall wäre.)
   Wenn $b\gt a$ gilt also: $\{c\mid c \text{ ist gemeinsamer Teiler von }a\text{ und }b\}$ $= \{c\mid c \text{ ist gemeinsamer Teiler von }b-a\text{ und }a\}$
   Für $a\gt b$ gilt es analog.
8. Seien $a,b$ positive, ganze Zahlen. Und es sei $r = a\ \mathrm{mod}\ b$.
   Zeigen Sie, dass gilt $\mathrm{ggT}(a,b)=\mathrm{ggT}(r,b)$.
   Beweis
   Beweis:
   Teil 1: Zeige, dass jeder Teiler von $a,b$ auch Teiler von $b, r$ ist.

   Es gilt: $r = a\ \mathrm{mod}\ b$, also $a=k\cdot b+r$ für ein $k\in \mathbb N$.
   Sei $d$ ein gemeinsamer Teiler von $a$ und $b$.
   Somit gilt $a=d\cdot x$ und $b=d\cdot y$ für irgendwelche ganzen Zahlen $x$ und $y$.
   

   Somit ist
   $\begin{array}{rcl} d\cdot x &=& a\\ &=& k\cdot b+r \\ &=& k\cdot d\cdot y+r\\ \end{array}$
   

   Es gilt also $dx=kdy+r$ und somit auch $r=dx-kdy = d(x-ky)$.
   Also teilt $d$ auch $r$ und $d$ teilt auch $b=dy$.

   Somit ist jeder Teiler, der $a$ und $b$ teilt auch ein Teiler von $r$ (und $b$).

   Teil 2: Jeder Teiler von $b,r$ ist auch Teiler von $a, b$.
   Sei $e$ ein gemeinsamer Teiler von $r,b$.

   Es gilt also $r=ex$ und $b=ey$ für ganze Zahlen $x$ und $y$.
   Da $r = a\ \mathrm{mod}\ b$ gilt: $a=k\cdot b+r$ für eine ganze Zahl $k$.
   Somit ist $a=kb+r = key+ex=e(ky+x)$.
   Also ist $e$ ein Teiler von $a$ (und natürlich auch von $b$).

   Da alle Teiler von $a,b$ auch Teiler von $b,r$ sind, gilt auch $\mathrm{ggT}(a,b)=\mathrm{ggT}(b,r)$.
   
   Anschauliche Alternative
   Sei $x_0=a$ und $x_1=b$.
   Sei $x_2=r=a\ \mathrm{mod}\ b$, so gilt: $a=k\cdot b+ r$, für eine ganze Zahl $k$.
   

   $\begin{array}{rcll} a &=& k\cdot b+ r\\ x_0 &=& k_1\cdot x_1 + x_2 & \quad 0\lt x_2\lt x_1\\ x_1 &=& k_2\cdot x_2 + x_3 & \quad 0\lt x_3\lt x_2\\ x_2 &=& k_3\cdot x_3 + x_4 & \quad 0\lt x_4\lt x_3\\ &\cdots \\ x_{n-2} &=& k_{n-1}\cdot x_{n-1} + x_n & \quad 0\lt x_n\lt x_{n-1}\\ x_{n-1} &=& k_n\cdot x_{n} + 0 & \end{array}$

   Die Folge $x_1, x_2, x_3, \ldots$ ist streng monoton fallend, d.h. die Werte werden immer kleiner und erreichen daher nach endlich vielen Schritten 0.

   Die Zahl $x_n$ ist Teiler von $x_{n-1}$, da $x_{n-1} = k_n\cdot x_{n} + 0$.
   Da $x_{n}$ die Zahl $x_{n-1}$ teilt teilt sie auch $x_{n-2}$.

   $x_{n-2} = k_{n-1}\cdot x_{n-1} + x_n $ $= k_{n-1}\cdot k_n\cdot x_{n} + x_n$ $= x_n(k_{n-1}\cdot k_n + 1)$.

   Da $x_{n}$ die Zahl $x_{n-2}$ teilt teilt sie auch $x_{n-3}$.

   $x_{n-3} = k_{n-2}\cdot x_{n-2} + x_{n-1}$
   $\phantom{x_{x-3}}= k_{n-2}(x_n(k_{n-1}\cdot k_n + 1)) + x_{n-1}$
   $\phantom{x_{x-3}} = k_{n-2}(x_n(k_{n-1}\cdot k_n + 1)) + k_n\cdot x_{n}$
   $\phantom{x_{x-3}} = x_n(k_{n-2}(k_{n-1}\cdot k_n + 1) + k_n)$
   

   Dies können wir fortführen bis zu $x_n$ teilt $x_0$.
   Also ist $x_n$ Teiler von $x_{n-1}, x_{n-2},\ldots, x_1=b, x_0=a$.
   Somit ist $x_n$ ein gemeinsamer Teiler von $a$ und $b$.

   Es gilt, dass $x_n$ der größte gemeinsame Teiler von $a$ und $b$ ist, denn jeder andere gemeinsame Teiler $d$ von $a$ und $b$ teilt auch $x_n$.
   Hierzu kann man das Vorgehen von oben für $d$ durchlaufen. Die erste Zeile zeigt, dass $d$ Teiler von $x_2$ ist, die zweite, dass es Teiler von $x_3$ ist, bis zur letzten Zeile, welche zeigt, dass $d$ Teiler von $x_n$ ist.
   Somit wäre jedes $d\leq x_n$.