\documentclass{uebungsblatt}
\author{Marek Kubica, kubica@in.tum.de}
\fach{Diskrete Strukturen}
\blatt{2}
\gruppe{11}

\begin{document}

\aufgabe

\teilaufgabe
1 ist Teiler von 5, da jede Zahl durch 1 teilbar ist. 1 ist keine Primzahl,
aber auch keine zusammengesetzte Zahl, da der Begriff erst für Zahlen
$> 1$ definiert ist.

$ ggT(986, 987) = 1 $

$ ggT(78, 240) = 6 $

\teilaufgabe
$ \frac{a}{b} = \frac{c}{d} $
wenn $ a \times d = b \times c $ (Multiplikation ``über kreuz''). Alternativ
sind die Brücke ebenfalls gleich wenn $ a = c \wedge b = d $. Wenn letzteres
nicht der Fall ist, kann es sein, dass die Brüche trotzdem gleich sind, in
dem Fall können die Brüche vereinfacht werden indem der Bruch 
$ \frac{a}{b} $ durch $ ggT(a, b) $ geteilt wird, der Bruch $ \frac{c}{d} $
hingegen durch $ ggT(c, d) $. Die so entstanden Brüche 
$ \frac{a_{1}}{b_{1}} $ und $ \frac{c_{1}}{d_{1}} $ können nun auf Gleichheit
verglichen werden indem man $ a_{1} = c_{1} \wedge b_{1} = d_{1} $ evaluiert.

\aufgabe

\teilaufgabe
$ \frac{a}{b} < \frac{x}{y} < \frac{c}{d} $

gilt immer wenn man die Brüche $ \frac{a}{b} $ und $ \frac{c}{d} $ so 
erweitert, dass sie den gemeinsamen Nenner $ b \times d $ haben, so dass
selbst wenn sie $ \frac{1}{3} $ und $ \frac{2}{3} $ sind, es noch genug
$ x, y \in \N $ gibt, dass die Aussage wahr ist. Dazu wird 
$ y = b \times d $ angenommen und $ x = (c \times d) - 1 $, was dazu führt,
dass $ \frac{x}{y} $ immer ein $ \frac{1}{b \times d} $ kleiner ist als
$ \frac{c}{d} $, jedoch nie kleiner gleich $ \frac{a}{b} $.

\teilaufgabe

Schritt 1: Man nehme $ a_{1}, b_{1} \in \Q $. Nun berechnet man
$ \frac{b_{1} - a_{1}}{2} $, welches in der Mitte zwischen $ a_{1} $ und
$ b_{1} $ ist. Diese Zahl wird nun $ b_{2} $ genannt.

Schritt 2: Durch das Aufstellen des Termes $ \frac{b_{2} - a_{1}}{2} $
kann man wiederrum die Zahl in der Mitte zwischen $ a_{1} $ und $ b_{2} $
bilden, die wiederrum immer $ \in \Q $ sind.

Schritt n: diese Teilung in immer weiter fortsetzbar.

\aufgabe

Behauptung: Es gibt kein $ y \in \R $ so dass $ y^{2} = 7 $. Also auch kein
$ y \in \R $ so dass $ y = \sqrt{7} $.

Annahme: $ \sqrt{7} $ ist rational, also durch den Bruch $ \frac{m}{n} $ mit
$ m, n \in \N $ darstellbar.

Beweis:

$ \sqrt{7} = \frac{m}{n} $

$ 7 = \frac{m^{2}}{n^{2}} $

$ m^{2} = 7n^{2} $

Zerlegung von $ m, n $ in Primfaktoren:

$ (m_{1} \times m_{2} \times \dots \times m_{a})^{2} = 
  7 \times (n_{1} \times n_{2} \times \dots \times n_{b})^{2} $

$ m_{1}^{2} \times m_{2}^{2} \times \dots \times m_{a}^{2} =
  2 \times n_{1}^{2} \times n_{2}^{2} \times \dots \times n_{b}^{2} $

$ \underbrace{
    m_{1} \times m_{1} \times m_{2} \times m_{2} \times \dots \times m_{a} \times m_{a}}_{\text{gerade Anzahl Primfaktoren}} =
  \underbrace{
    2 \times n_{1} \times n_{1} \times n_{2} \times n_{2} \times \dots n_{b} \times n_{b}}_{\text{ungerade Anzahl Primfaktoren, wegen dem} \times 2} 
$

Kann so nie sein $ \Rightarrow $ Widerspruch.

\aufgabe

Um die Ziffer die an Index $i$ steht herauszufinden, muss man die Ziffern an 
der Stelle $ i + 1 $ kennen, dazu kann man sich einer rekursiven Definition
bedienen:

$ c_{n} = \overbrace{(\underbrace{(a_{n} + b_{n})}_{\text{Summe der Ziffern } a_{n}, b_{n}} + (\underbrace{(a_{n+1} + b_{n+1}) - \overbrace{(a_{n+1} + b_{n+1}) \% 10}^{\text{Einerstelle}}) / 10}_{\text{Zehnerstelle}}) \% 10}^{\text{Ziffer } \in \N_{0}} $

Zunächst ist es nötig, den Übertrag zu berechnen. Dabei wird die Summe von 
$ a_{n+1} $ und $ b_{n+1} $ gebildet. Da diese $ > 9 $ sein kann, wird Modulo
10 gerechnet, um die ``Einerstelle'' zu bekommen. Diese wird dann von der Summe
von $ a_{n+1}, b_{n+1} $ abgezogen, womit man einen Übertrag von 0 
(kein Übertrag) oder 10 (``Eins gemerkt'') bekommt. Diese Zahl wird durch 10
geteilt um auf  diese Weise den Übertrag von 0 oder 1 zu bekommen. Dieser 
Übertrag kann nun auf die Summe von $ a_{n}, b_{n} $ aufaddiert und diese Zahl
wiederrum Modulo 10 berechnet um auf ein Intervall von 0 bis 9 zu kommen.

\end{document}