Kurs:Zahlentheorie (Osnabrück 2016-2017)/Arbeitsblatt 3/latex

\setcounter{section}{3}

\zwischenueberschrift{Übungsaufgaben}

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

Bestimme in $\Z$ mit Hilfe des euklidischen Algorithmus den \definitionsverweis {größten gemeinsamen Teiler}{}{} von $3711$ und $4115$.

}
{} {}

\inputaufgabegibtloesung
{}
{

Bestimme in $\Z$ mit Hilfe des euklidischen Algorithmus den \definitionsverweis {größten gemeinsamen Teiler}{}{} von $71894$ und $45327$.

}
{} {}

\inputaufgabegibtloesung
{}
{

Man bestimme den \definitionsverweis {größten gemeinsamen Teiler}{}{} von \mathkor {} {3146} {und} {1515} {} und man gebe eine Darstellung des $\operatorname{ggT}$ von \mathkor {} {3146} {und} {1515} {} mittels dieser Zahlen an.

}
{} {}

\inputaufgabe
{}
{

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

}
{} {}

\inputaufgabe
{}
{

Die Beschreibungsseite des folgenden Bildes behauptet, etwas mit dem euklidischen Algorithmus zu tun zu haben. Erläutere dies. Welche Eigenschaften des euklidischen Algorithmus sind in dem Bild sichtbar? Beweise diese Eigenschaften des Algorithmus.

\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Euclidean_algorithm_running_time_X_Y.png} }
\end{center}
\bildtext {} }

\bildlizenz { Euclidean algorithm running time X Y.png } {} {Fredrik} {en.wikipedia.org} {PD} {}

}
{} {}

\inputaufgabe
{}
{

Die Wasserspedition \anfuehrung{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?

}
{} {}

\inputaufgabe
{}
{

Bestimme in ${\mathbb C}[X]$ mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler der beiden Polynome \mathkor {} {X^3+ (2- { \mathrm i} )X^2+ 4} {und} {(3- { \mathrm i})X^2+5 X -3} {.}

}
{} {}

\inputaufgabe
{}
{

Bestimme in $\Q[X]$ mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler der beiden Polynome \mathkor {} {2X^4-7X^2+\frac{5}{2}X +3} {und} {X^3+1} {.}

}
{} {}

\inputaufgabe
{}
{

Bestimme in ${\mathbb F}_7[X]$ mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler der beiden Polynome \mathkor {} {P=X^3+ 6X^2+ 4} {und} {Q= X^2+ 3X+2} {.}

}
{} {}

\inputaufgabe
{}
{

Bestimme in
\mathl{\Z/(11)[X]}{} den \zusatzklammer {normierten} {} {} größten gemeinsamen Teiler der beiden Polynome
\mathdisp {X^4+2X^3 +2X^2 +3 \, \, \, \text{ und } \, \, \, X^2+ 7X + 10} { . }

}
{} {}

\inputaufgabegibtloesung
{}
{

Bestimme in
\mathl{\Z[ { \mathrm i} ]}{} mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von
\mathl{23+2 { \mathrm i}}{} und
\mathl{1+23 { \mathrm i}}{.}

}
{} {}

\inputaufgabe
{}
{

Zeige, dass im Polynomring
\mathl{K[X,Y]}{} nicht das Lemma von Bezout gilt.

}
{} {}

\inputaufgabe
{}
{

Es sei $R$ ein \definitionsverweis {kommutativer Ring}{}{} und sei
\mathdisp {{\mathfrak a}_1 \subseteq {\mathfrak a}_2 \subseteq {\mathfrak a}_3 \subseteq \ldots} { }
eine aufsteigende Kette von \definitionsverweis {Idealen}{}{.} Zeige, dass die \definitionsverweis {Vereinigung}{}{}
\mathl{\bigcup_{n \in \N} {\mathfrak a}_n}{} ebenfalls ein Ideal ist. Zeige durch ein einfaches Beispiel, dass die Vereinigung von Idealen im Allgemeinen kein Ideal sein muss.

}
{} {}

\inputaufgabe
{}
{

Zeige, dass in einem \definitionsverweis {Hauptidealbereich}{}{} $R$ zu beliebigen Elementen
\mathl{a_1 , \ldots , a_n \in R}{} sowohl ein \definitionsverweis {größter gemeinsame Teiler}{}{} als auch ein \definitionsverweis {kleinstes gemeinsames Vielfaches}{}{} existieren. Wie kann man sie berechnen, wenn die Primfaktorzerlegungen der Elemente bekannt sind?

}
{} {}

Für $\Z$ lässt sich die Existenz einer Zerlegung in Primzahlen, also in irreduzible Elemente, einfach direkt zeigen.


\inputaufgabegibtloesung
{}
{

Zeige durch Induktion, dass jede natürliche Zahl
\mavergleichskette
{\vergleichskette
{n }
{ \geq }{2 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} eine Zerlegung in \definitionsverweis {Primzahlen}{}{} besitzt.

}
{} {}

\inputaufgabe
{}
{

Finde einen Primfaktor der Zahl
\mathl{2^{25}+1}{.}

}
{} {}

\inputaufgabegibtloesung
{}
{

Bestimme die \definitionsverweis {Primfaktorzerlegung}{}{} von $1728$.

}
{} {}

\inputaufgabegibtloesung
{}
{

Wir betrachten das kleine Einmaleins als eine Verknüpfungstabelle, in der alle Produkte
\mathl{i \cdot j}{} mit
\mavergleichskette
{\vergleichskette
{1 }
{ \leq }{ i,j }
{ \leq }{ 9 }
{ }{ }
{ }{ }
} {}{}{} stehen. Bestimme die \definitionsverweis {Primfaktorzerlegung}{}{} des Produktes über alle Einträge in der Tabelle.

}
{} {}

\inputaufgabegibtloesung
{}
{

Man gebe zwei Primfaktoren von
\mathl{2^{35} -1}{} an.

}
{} {}

\inputaufgabe
{}
{

Es sei $p$ eine \definitionsverweis {Primzahl}{}{.} Zeige, dass
\mavergleichskettedisp
{\vergleichskette
{ \binom { p } { k } }
{ \equiv} { 0 \mod p }
{ } { }
{ } { }
{ } { }
} {}{}{} für alle
\mavergleichskette
{\vergleichskette
{ k }
{ = }{ 1 , \ldots , p-1 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} ist.

}
{} {}

\inputaufgabe
{}
{

Es seien
\mathl{a,b \in \N_+}{.} Zeige, dass
\mavergleichskettedisp
{\vergleichskette
{a^b }
{ =} {b^a }
{ } { }
{ } { }
{ } { }
} {}{}{} genau dann gilt, wenn
\mavergleichskettedisp
{\vergleichskette
{a }
{ =} {b }
{ } { }
{ } { }
{ } { }
} {}{}{} ist oder wenn
\mavergleichskette
{\vergleichskette
{a }
{ = }{2 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} und
\mavergleichskette
{\vergleichskette
{b }
{ = }{4 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} ist \zusatzklammer {oder umgekehrt} {} {.}

}
{} {}

\inputaufgabe
{}
{

Es sei $R$ ein \definitionsverweis {kommutativer Ring}{}{} und
\mathbed {p \in R} {}
{p \neq 0} {}
{} {} {} {.} Zeige, dass $p$ genau dann ein \definitionsverweis {Primelement}{}{} ist, wenn der \definitionsverweis {Restklassenring}{}{}
\mathl{R/(p)}{} ein \definitionsverweis {Integritätsbereich}{}{} ist.

}
{} {}

\zwischenueberschrift{Aufgaben zum Abgeben}

\inputaufgabe
{2}
{

Finde einen \definitionsverweis {Primfaktor}{}{} der Zahl
\mathl{2^{25}-1}{.}

}
{} {}

\inputaufgabe
{3}
{

Bestimme in
\mathl{{\Z}[{ \mathrm i}]}{} mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von
\mathl{35+18{ \mathrm i}}{} und
\mathl{8+11{ \mathrm i}}{.}

}
{} {}

\inputaufgabe
{3}
{

Bestimme in ${\mathbb F}_5[X]$ mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler der beiden Polynome \mathkor {} {P=X^4+3 X^3+ X^2+4X+2} {und} {Q=2X^3+4 X^2+ X+3} {.}

}
{} {}

In der folgenden Aufgabe wird der Logarithmus verwendet.


\inputaufgabe
{4 (3+1)}
{

Betrachte die reellen Zahlen $\R$ als $\mathbb Q$-Vektorraum. Zeige, dass die Menge der reellen Zahlen $\ln p$, wobei $p$ durch die Menge der Primzahlen läuft, \definitionsverweis {linear unabhängig}{}{} ist. Bleibt das Ergebnis gültig, wenn man den natürlichen Logarithmus $\ln$ durch einen Logarithmus zu einer anderen Basis ersetzt?

}
{} {}

\inputaufgabe
{3 (2+1)}
{

Es sei
\mavergleichskette
{\vergleichskette
{r }
{ \in }{ \N }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.}

a) Finde $r$ aufeinander folgende natürliche Zahlen \zusatzklammer {also
\mathl{n, n+1 , \ldots , n+r-1}{}} {} {,} die alle nicht prim sind.

b) Finde unendlich viele solcher primfreien $r$-\anfuehrung{Intervalle}{.}

}
{} {}

\inputaufgabe
{6 (2+2+2)}
{

Zu einer natürlichen Zahl $n$ bezeiche $T(n)$ die Anzahl der positiven Teiler von $n$. Zeige die folgenden Aussagen über $T(n)$.

a) Sei
\mavergleichskette
{\vergleichskette
{n }
{ = }{p_1^{r_1} \cdots p_k^{r_k} }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} die \definitionsverweis {Primfaktorzerlegung}{}{} von $n$. Dann ist
\mavergleichskettedisp
{\vergleichskette
{ T(n) }
{ =} {(r_1+1) (r_2+1) \cdots (r_k+1) }
{ } { }
{ } { }
{ } { }
} {}{}{.}

b) Für teilerfremde Zahlen $n$ und $m$ gilt
\mavergleichskette
{\vergleichskette
{T(nm) }
{ = }{T(n)T(m) }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.}

c) Bestimme die Anzahl der Teiler von $20!$.

}
{} {}