Kurs:Diskrete Mathematik (Osnabrück 2020)/Arbeitsblatt 8

Die Pausenaufgabe

Aufgabe

Es stehen zwei Eimer ohne Markierungen zur Verfügung, ferner eine Wasserquelle. Der eine Eimer hat ein Fassungsvermögen von ${}5$ und der andere ein Fassungsvermögen von ${}7$ Litern. Zeige, dass man allein durch Auffüllungen, Ausleerungen und Umschüttungen erreichen kann, dass in einem Eimer genau ein Liter Wasser enthalten ist.

Übungsaufgaben

Aufgabe *

Finde eine Darstellung der ${}1$ für das Zahlenpaar ${}11$ und ${}13$.

Aufgabe

Finde eine Darstellung der ${}1$ für die folgenden Zahlenpaare: ${}5$ und ${}7$; ${}20$ und ${}27$; ${}23$ und ${}157$.

Aufgabe

Die Wasserspedition „Alles im Eimer“ verfügt über ${}77$-, ${}91$- und ${}143$-Liter Eimer, die allerdings keine Markierungen haben. Sie erhält den Auftrag, insgesamt genau einen Liter Wasser von der Nordsee in die Ostsee zu transportieren. Wie kann sie den Auftrag erfüllen?

Aufgabe

Es seien ${}a$ und ${}b$ teilerfremde natürliche Zahlen. Es stehen beliebig viele Eimer ohne Markierungen zur Verfügung, deren Fassungsvermögen ${}a$ bzw. ${}b$ ist. Zeige, dass man allein durch Auffüllungen, Ausleerungen und Umschüttungen erreichen kann, dass in einem Eimer genau ein Liter Wasser enthalten ist.

Aufgabe *

Es stehen zwei Eimer ohne Markierungen zur Verfügung, ferner eine Wasserquelle. Der eine Eimer hat ein Fassungsvermögen von ${}a$ und der andere ein Fassungsvermögen von ${}b$ Litern, wobei ${}a$ und ${}b$ teilerfremd seien. Zeige, dass man allein durch Auffüllungen, Ausleerungen und Umschüttungen erreichen kann, dass in einem Eimer genau ein Liter Wasser enthalten ist.

Aufgabe *

Beweise das Lemma von Bezout für teilerfremde natürliche Zahlen ${}a$ und ${}b$ durch Induktion über das Maximum von ${}a$ und ${}b$.

Aufgabe *

Zeige, dass es zu ganzen Zahlen ${}d,n$ mit ${}d>0$ eindeutig bestimmte ganze Zahlen ${}q,r$ mit ${}0\leq r<d$ und mit

${}n=dq+r\,$

gibt.

Aufgabe

Es seien ${}n,d$ positive Zahlen und es sei

${}n=qd+r\,$

mit ${}q\in \mathbb {N}$ und ${}r$ zwischen ${}0$ und ${}d-1$. Wie erhält man daraus die Division mit Rest von ${}-n$ durch ${}d$?

Aufgabe *

Zeige, dass es zu ganzen Zahlen ${}d,n$ mit ${}d>0$ eindeutig bestimmte ganze Zahlen ${}k,s$ mit

${}n=kd+s\,$

und mit

${}-{\frac {d}{2}}<s\leq {\frac {d}{2}}\,$

gibt.

Aufgabe

Es seien ${}q,d,s\in \mathbb {N}$ mit ${}d\geq 1$ und ${}n=qd+s$. Zeige, dass der Rest von ${}n$ bei Division durch ${}d$ gleich dem Rest von ${}s$ bei Division durch ${}d$ ist.

Aufgabe

Es sei ${}d$ eine positive natürliche Zahl. Es seien ${}a,b$ natürliche Zahlen und es seien ${}r$ bzw. ${}s$ die Reste von ${}a$ bzw. ${}b$ bei Division durch ${}d$. Zeige, dass der Rest von ${}a+b$ bei Division durch ${}d$ gleich dem Rest von ${}r+s$ bei Division durch ${}d$ ist. Formuliere und beweise die entsprechende Aussage für die Multiplikation.

Kommentar:

Die Division mit Rest durch ${}d$ besagt, dass es zu jedem ${}a$ eindeutige Elemente ${}q,r$ mit ${}r$ zwischen ${}0$ und ${}d-1$ und mit

${}a=qd+r\,$

gibt. Bei der Aufgabe geht es um die Frage, wie sich die Reste bei den üblichen Verknüpfungen verhalten. Sei

${}b=pd+s\,.$

Es wäre nun zu schön, wenn der Rest von ${}a+b$ gleich ${}r+s$ wäre. Dies kann aber nicht sein, da ${}r+s$ größer als ${}d$ sein kann, der Rest aber immer kleiner als ${}d$ ist. Es gilt aber das zweitschönste, nämlich dass der Rest von ${}a+b$ gleich dem Rest von ${}r+s$ ist. Man muss also eventuell einmal ${}d$ abziehen. Der Grund ist einfach

${}a+b=qd+r+pd+s=(q+p)d+(r+s)=(q+p+1)d+(r+s-d)\,,$

wobei die letzte Umformung bei ${}r+s\geq d$ durchzuführen ist.

Die Menge

$\mathbb {Z} d=\{kd\mid k\in \mathbb {Z} \}$

besteht aus allen Vielfachen von ${}d$. Um die Division durch ${}d$ zu studieren, betrachten wir allgemeiner die Menge

$\mathbb {Z} d+a=\{kd+a\mid k\in \mathbb {Z} \}$

für jedes ${}a\in \mathbb {Z}$. Wie kann man diese Menge charakterisieren? Was kann man über die Menge

$\mathbb {Z} /(d):=\{\mathbb {Z} d+a\mid a\in \mathbb {Z} \}$

sagen? Insbesondere ist ${}\mathbb {Z} /(d)$ endlich oder unendlich?

Um diese Fragen zu beantworten, soll man die Bedingung

$\mathbb {Z} d+a=\mathbb {Z} d+b$

betrachten. Es ist leicht zu sehen, dass diese Bedingung genau dann gilt, wenn ${}a-b$ ein Vielfaches von ${}d$ ist, d.h. ${}a$ und ${}b$ den gleichen Rest bei Division durch ${}d$ haben. Also gilt

$\mathbb {Z} d+a=\mathbb {Z} d+r,$

wobei ${}r$ der Rest von ${}a$ bei Division durch ${}d$ und diese Menge besteht aus allen Zahlen, die den Rest ${}r$ bei Division durch ${}d$ besitzen. Insbesondere ist ${}\mathbb {Z} /(d)$ endlich und besteht aus ${}d$ Elementen:

$\mathbb {Z} /(d)=\{\mathbb {Z} d+r\mid r=0,1,\dots ,d-1\}.$

Außerdem ist ${}\mathbb {Z}$ die disjunkte Vereinigung der Mengen ${}\mathbb {Z} d+r$ für ${}r=0,1,\dots ,d-1$.

Die Aussagen dieser Aufgabe besagen, dass

${\begin{aligned}(\mathbb {Z} d+a)+(\mathbb {Z} d+b)&=\mathbb {Z} d+(a+b),\\(\mathbb {Z} d+a)(\mathbb {Z} d+b)&=\mathbb {Z} d+ab\end{aligned}}$

für alle ${}a,b\in \mathbb {Z}$, d.h. die Addition und die Multiplikation auf ${}\mathbb {Z}$ induzieren die entsprechenden Verknüpfungen auf ${}\mathbb {Z} /(d)$. Mit obigen Beobachtungen kann man diese Aussagen unmittelbar zeigen. Man kann auch zeigen, dass die Menge ${}\mathbb {Z} /(d)$ mit diesen Verknüpfungen einen kommutativen Ring bildet. Außerdem ist ${}\mathbb {Z} /(d)$ genau dann ein Körper, wenn ${}d$ eine Primzahl ist. Das kommt in der Vorlesung 12 dran.

 

Aufgabe

Zeige, dass für zwei ganze Zahlen ${}a,b\in \mathbb {Z}$ die folgenden Beziehungen äquivalent sind.

1. ${}a$ teilt ${}b$ (also ${}a{|}b$).
2. ${}b\in \mathbb {Z} a$.
3. ${}\mathbb {Z} b\subseteq \mathbb {Z} a$.

Aufgabe

In welcher Beziehung steht Aufgabe 8.13 zu Lemma 7.16?

Aufgabe *

Es seien ${}a_{1},\ldots ,a_{k}$ ganze Zahlen und ${}H=(a_{1},\ldots ,a_{k})={\left\{n_{1}a_{1}+n_{2}a_{2}+\cdots +n_{k}a_{k}\mid n_{j}\in \mathbb {Z} \right\}}$ die davon erzeugte Untergruppe. Zeige, dass eine ganze Zahl ${}t$ genau dann ein gemeinsamer Teiler der ${}a_{1},\ldots ,a_{k}$ ist, wenn ${}H\subseteq \mathbb {Z} t$ ist, und dass ${}t$ genau dann ein größter gemeinsamer Teiler ist, wenn ${}H=\mathbb {Z} t$ ist.

Aufgabe

Es seien (beliebige viele) gemalte Pfeile der Länge ${}7$ und der Länge ${}12$ gegeben. Wie muss man die Pfeile hintereinanderlegen (wobei immer ein Pfeilende an der Pfeilspitze des Vorgängerpfeils anliegt), damit insgesamt ein Gesamtpfeil der Länge ${}-1$ entsteht?

Aufgabe *

Auf einer Baustelle gibt es eine große Waage mit zwei Schalen und (beliebig viele) Gewichte der Schwere ${}12$ bzw. ${}50$ Kilogramm.

1. Erläutere, wie man damit sechs Kilogramm Sand abwiegen kann.
2. Bestimme, welche Massen man damit abwiegen kann.

Aufgabe

Auf den ganzen Zahlen ${}\mathbb {Z}$ lebe eine Kolonie von Flöhen, und jeder Flohsprung geht fünf Einheiten weit (in beide Richtungen). Wie viele Flohpopulationen gibt es? Wie kann man einfach charakterisieren, ob zwei Flöhe zur gleichen Population gehören oder nicht?

Aufgabe

Bestimme in ${}\mathbb {Z}$ mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von ${}5439$ und ${}3871$.

Aufgabe

Bestimme in ${}\mathbb {Z}$ mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von ${}2956$ und ${}2444$.

Aufgabe *

Bestimme in ${}\mathbb {Z}$ mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von ${}1085$ und ${}806$ und schreibe die beiden Zahlen als Vielfache des größten gemeinsamen Teilers.

Aufgabe *

Wir betrachten eine (einfachere, aber langsamere) Variante des euklidischen Algorithmus zur Bestimmung des größten gemeinsamen Teilers zu zwei gegebenen natürlichen Zahlen ${}a,b$.

Der Algorithmus geht folgendermaßen. Wenn ${}a\neq b$ ist, so ersetzte das Paar ${}(a,b)$ durch das Paar, das aus der kleineren Zahl und der Differenz zwischen der kleineren und der größeren Zahl besteht. Wiederhole dies rekursiv. Wenn ${}a=b$ ist, so ist man fertig und es wird das Ergebnis ${}a$ ausgegeben.

1. Führe diesen Algorithmus für das Paar ${}(7,3)$ durch.
2. Zeige, dass dieser Algorithmus nach endlich vielen Schritten aufhört.
3. Zeige, dass dieser Algorithmus korrekt ist, also wirklich den größten gemeinsmen Teiler ausgibt.
4. Man gebe für jedes ${}n$ ein Beispiel, wo der euklidische Algorithmus nach einem Schritt fertig ist, wo aber die Variante ${}n$ Schritte benötigt.

Aufgabe

Es sei

${}p\neq 2,5\,$

eine Primzahl. Zeige, dass es eine natürliche Zahl der Form (im Dezimalsystem)

$111\ldots 111$

gibt, die ein Vielfaches von ${}p$ ist.

Kommentar:

Wir bezeichen mit ${}a_{n}$ die Zahl 11...1, die aus ${}n$ Einsen besteht. Sei ${}r_{n}$ der Rest von ${}a_{n}$ bei Division durch ${}p$. Die Schwierigkeit dieser Aufgabe liegt darin, dass ${}p$ unbekannt ist und somit kann man ${}r_{n}$ nicht berechnen. Hier ist die Schlüsselidee: man kann ${}r_{n}$ nicht berechnen, aber man weiß sicher, dass ${}r_{n}\in \{0,1,\dots ,p-1\}$. Also ist die Menge ${}\{r_{n}\mid n\in \mathbb {N} \}$ endlich. Somit existieren ${}k,m\in \mathbb {N}$ mit ${}k<m$, sodass ${}r_{k}=r_{m}$ (siehe auch Lemma 1.4.) Dies bedeutet, dass ${}a_{m}-a_{k}$ ein Vielfaches von ${}p$ ist. Was ist nun ${}a_{m}-a_{k}$? Wo verwendet man hier die Voraussetzung, dass ${}p\neq 2,5$ eine Primzahl ist?

 

Aufgabe

Kaninchen werden bekanntlich immer zur Monatsmitte geboren, die Tragzeit beträgt einen Monat und die Geschlechtsreife erreichen sie im Alter von zwei Monaten. Jeder Wurf besteht aus genau einem Paar, und alle leben ewig.

Wir starten im Monat ${}1$ mit einem Paar, das einen Monat alt ist. Es sei ${}f_{n}$ die Anzahl der Kaninchenpaare im ${}n$-ten Monat, also ${}f_{1}=1$, ${}f_{2}=1$. Beweise durch Induktion die Rekursionsformel

${}f_{n+2}=f_{n+1}+f_{n}\,.$

Diese Zahlfolge nennt man die Folge der Fibonacci-Zahlen. Wie viele der ${}f_{n}$ Paare sind im ${}n$-ten Monat reproduktionsfähig?

Die Fibonacci-Zahlen sind somit ${}1,1,2,3,5,8,13,21,34,\ldots$

Aufgabe

Wende auf zwei aufeinander folgende Fibonacci-Zahlen den euklidischen Algorithmus an. Welche Gesetzmäßigkeit tritt auf?

Aufgabe *

Beweise durch Induktion die Simpson-Formel oder Simpson-Identität für die Fibonacci-Zahlen ${}f_{n}$. Sie besagt (für $n\geq 2$)

${}f_{n+1}f_{n-1}-f_{n}^{2}=(-1)^{n}\,.$

Aufgabe *

Es seien ${}a_{1},\ldots ,a_{k}$ ganze Zahlen. Zeige, dass

${}\mathbb {Z} a_{1}\cap \mathbb {Z} a_{2}\cap \ldots \cap \mathbb {Z} a_{k}=\mathbb {Z} u\,$

ist, wobei ${}u$ das kleinste gemeinsame Vielfache der ${}a_{1},\ldots ,a_{k}$ ist.

Aufgabe *

Zeige, dass für natürliche Zahlen ${}a,b,g$ folgende Aussagen gelten.

1. Für teilerfremde ${}a,b$ ist

   ${}\operatorname {kgV} \,(a,b)=ab\,.$

2. Es gibt ${}c,d\in \mathbb {Z}$ mit

   $a=c\cdot \operatorname {ggT} \,(a,b)\,\,{\text{ und }}\,\,b=d\cdot \operatorname {ggT} \,(a,b),$

   wobei ${}c,d$ teilerfremd sind.

3. Es ist

   ${}\operatorname {kgV} \,(ga,gb)=g\cdot \operatorname {kgV} \,(a,b)\,.$

4. Es ist

   ${}\operatorname {ggT} \,(a,b)\cdot \operatorname {kgV} \,(a,b)=ab\,.$

Aufgabe

Es sei ${}{\mathbb {P} }$ die Menge der Primzahlen und ${}\mathbb {N} ^{\mathbb {P} }$ die Menge aller Abbildungen von ${}{\mathbb {P} }$ nach ${}\mathbb {N}$. Wir betrachten die Abbildung

$\varphi \colon \mathbb {N} _{+}\longrightarrow \mathbb {N} ^{\mathbb {P} },\,n\longmapsto (a_{p})_{p\in {\mathbb {P} }},$

die jeder natürlichen Zahl ${}n\neq 0$ das Exponententupel ${}(a_{p})_{p\in {\mathbb {P} }}=(a_{p}(n))_{p\in {\mathbb {P} }}$ zuordnet. Man betrachtet also die eindeutige Primfaktorzerlegung

${}n=\prod _{p\in {\mathbb {P} }}p^{a_{p}}\,,$

wobei sich das Produkt über alle Primzahlen erstreckt und wobei nur endlich viele Exponenten ungleich ${}0$ sind.

1. Zeige, dass ${}\varphi$ injektiv ist.
2. Bestimme das Bild von ${}\varphi$.
3. Es sei ${}\mathbb {N} _{+}$ mit der Teilbarkeitsrelation und ${}\mathbb {N} ^{\mathbb {P} }$ mit der Produktordnung versehen. Zeige, dass ${}\varphi$ eine ordnungsvolltreue Abbildung ist.

Aufgabe

Zeige, dass es ganze Zahlen ${}a,b$ derart gibt, dass

${}{\frac {1}{100}}=a{\frac {1}{4}}+b{\frac {1}{25}}\,$

gilt. Finde solche Zahlen.

Aufgabe

Finde ganze Zahlen ${}a,b$ derart, dass

${}{\frac {1}{15}}=a{\frac {1}{3}}+b{\frac {1}{5}}\,$

gilt.

Aufgabe *

Es seien ${}a,b$ positive natürliche Zahlen. Die Summe der Stammbrüche ist dann

${}{\frac {1}{a}}+{\frac {1}{b}}={\frac {b+a}{ab}}\,.$

a) Zeige, dass bei ${}a,b$ teilerfremd diese Darstellung gekürzt ist.

b) Zeige, dass im Allgemeinen diese Darstellung nicht gekürzt sein muss.

Aufgabe *

Zeige, dass jede rationale Zahl ${}z\neq 0$ eine eindeutige Darstellung der Form

${}z=\pm \prod _{p}p^{\exp _{p}(z)}\,$

besitzt, wobei das (endliche) Produkt sich über Primzahlen erstreckt und die Exponenten ${}{\exp _{p}(z)}\in \mathbb {Z}$ sind.

Aufgabe

Es sei ${}M\subseteq \mathbb {N} _{+}$ diejenige Teilmenge, die aus allen natürlichen Zahlen besteht, die bei Division durch ${}4$ den Rest ${}1$ besitzen, also ${}M=\{1,5,9,13,17,{\ldots }\}$. Zeige, dass man ${}441$ innerhalb von ${}M$ auf zwei verschiedene Arten in Faktoren zerlegen kann, die in ${}M$ nicht weiter zerlegbar sind.

Aufgaben zum Abgeben

Aufgabe (2 Punkte)

Bestimme in ${}\mathbb {Z}$ mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von ${}1983$ und ${}1528$.

Aufgabe (4 Punkte)

Bestimme den größten gemeinsamen Teiler von ${}4199,2431$ und ${}3553$, sowie eine Darstellung desselben als eine Linearkombination der gegebenen Zahlen.

Aufgabe (2 Punkte)

Es seien ${}a_{1},a_{2},\ldots ,a_{k}$ ganze Zahlen. Zeige, dass die Menge

${}H:={\left\{n_{1}a_{1}+n_{2}a_{2}+\cdots +n_{k}a_{k}\mid n_{j}\in \mathbb {Z} \right\}}\,$

eine Untergruppe von ${}\mathbb {Z}$ ist.

Aufgabe (4 Punkte)

Es seien ${}a,b$ teilerfremde natürliche Zahlen. Zeige, dass jede natürliche Zahl

${}n\geq ab\,$

eine Darstellung

${}n=xa+yb\,$

mit ${}x,y\in \mathbb {N}$ besitzt.

Aufgabe (3 Punkte)

Alle Flöhe leben auf einem unendlichen Zentimeter-Band. Ein Flohmännchen springt bei jedem Sprung ${}78$ cm und die deutlich kräftigeren Flohweibchen springen mit jedem Sprung ${}126$ cm. Die Flohmännchen Florian, Flöhchen und Carlo sitzen in den Positionen ${}-123,55$ und ${}-49$. Die Flohweibchen Flora und Florentina sitzen in Position ${}17$ bzw. ${}109$. Welche Flöhe können sich treffen?

Aufgabe (5 Punkte)

Wir betrachten eine digitale Uhr, die ${}24$ Stunden, ${}60$ Minuten und ${}60$ Sekunden anzeigt. Zur Karnevalszeit läuft sie aber nicht in Sekundenschritten, sondern addiert, ausgehend von der Nullstellung, in jedem Zählschritt immer ${}11$ Stunden, ${}11$ Minuten und ${}11$ Sekunden dazu. Wird bei dieser Zählweise jede mögliche digitale Anzeige erreicht? Nach wie vielen Schritten kehrt zum ersten Mal die Nullstellung zurück?

Aufgabe (3 Punkte)

Es seien ${}p$ und ${}q$ verschiedene Primzahlen. Zeige, dass es ganze Zahlen ${}a,b$ derart gibt, dass

${}{\frac {1}{pq}}=a{\frac {1}{p}}+b{\frac {1}{q}}\,$

gilt.