Elementare und algebraische Zahlentheorie/16/Klausur mit Lösungen/latex
%Daten zur Institution
%\input{Dozentdaten}
%\renewcommand{\fachbereich}{Fachbereich}
%\renewcommand{\dozent}{Prof. Dr. . }
%Klausurdaten
\renewcommand{\klausurgebiet}{ }
\renewcommand{\klausurtyp}{ }
\renewcommand{\klausurdatum}{ . 20}
\klausurvorspann {\fachbereich} {\klausurdatum} {\dozent} {\klausurgebiet} {\klausurtyp}
%Daten für folgende Punktetabelle
\renewcommand{\aeins}{ 3 }
\renewcommand{\azwei}{ 3 }
\renewcommand{\adrei}{ 2 }
\renewcommand{\avier}{ 0 }
\renewcommand{\afuenf}{ 0 }
\renewcommand{\asechs}{ 1 }
\renewcommand{\asieben}{ 0 }
\renewcommand{\aacht}{ 4 }
\renewcommand{\aneun}{ 4 }
\renewcommand{\azehn}{ 3 }
\renewcommand{\aelf}{ 0 }
\renewcommand{\azwoelf}{ 4 }
\renewcommand{\adreizehn}{ 0 }
\renewcommand{\avierzehn}{ 0 }
\renewcommand{\afuenfzehn}{ 0 }
\renewcommand{\asechzehn}{ 0 }
\renewcommand{\asiebzehn}{ 24 }
\renewcommand{\aachtzehn}{ }
\renewcommand{\aneunzehn}{ }
\renewcommand{\azwanzig}{ }
\renewcommand{\aeinundzwanzig}{ }
\renewcommand{\azweiundzwanzig}{ }
\renewcommand{\adreiundzwanzig}{ }
\renewcommand{\avierundzwanzig}{ }
\renewcommand{\afuenfundzwanzig}{ }
\renewcommand{\asechsundzwanzig}{ }
\punktetabellesechzehn
\klausurnote
\newpage
\setcounter{section}{K}
\inputaufgabepunkteloesung
{3}
{
Definiere die folgenden \zusatzklammer {kursiv gedruckten} {} {} Begriffe. \aufzaehlungsechs{Ein \stichwort {euklidischer Bereich} {} $R$.
}{Ein
\stichwort {Ideal} {}
\mathl{{\mathfrak a} \subseteq R}{} in einem
\definitionsverweis {kommutativen Ring}{}{}
$R$.
}{Das \stichwort {Legendre-Symbol} {.}
}{Die \stichwort {Riemannsche Zetafunktion} {.}
}{Eine \stichwort {Mersennesche Primzahl} {.}
}{Eine \stichwort {Sophie-Germain-Primzahl} {.} }
}
{
\aufzaehlungsechs{Ein euklidischer Bereich ist ein
\definitionsverweis {Integritätsbereich}{}{}
$R$, für den eine Abbildung
\mathl{\delta: R \setminus \{0\} \to \N}{} existiert, die die folgende Eigenschaft erfüllt:
Für Elemente
\mathl{a , b}{} mit
\mathl{b \neq 0}{} gibt es
\mathl{q , r \in R}{} mit
\mathdisp {a = qb+r \text{ und } r=0 \text{ oder } \delta (r)< \delta (b)} { . }
}{Ein Ideal ist eine nichtleere Teilmenge ${\mathfrak a} \subseteq R$, für die die beiden folgenden Bedingungen erfüllt sind:
\aufzaehlungzwei {Für alle
\mathl{a,b \in {\mathfrak a}}{} ist auch
\mathl{a+b \in {\mathfrak a}}{.}
} {Für alle
\mathl{a \in {\mathfrak a}}{} und
\mathl{r \in R}{} ist auch
\mathl{ra \in {\mathfrak a}}{.}}
}{Für eine ungerade Primzahl $p$ und eine zu $p$ teilerfremde Zahl
\mathl{k \in \Z}{} definiert man das Legendre-Symbol durch
\mavergleichskettedisphandlinks
{\vergleichskettedisphandlinks
{ \left( \frac{ k }{ p }\right)
}
{ \defeq} {\begin{cases} 1, \text{ falls } k \text{ quadratischer Rest modulo } p \text{ ist}, \\
- 1, \text{ falls } k \text{ kein quadratischer Rest modulo } p \text{ ist}.
\end{cases}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
}{Die Riemannsche $\zeta$-Funktion ist für
\mathl{s \in {\mathbb C}}{} mit Realteil
\mathl{\operatorname{Re} \, { \left( s \right) } > 1}{} durch
\mavergleichskettedisp
{\vergleichskette
{ \zeta(s)
}
{ =} { \sum_{n = 1}^\infty \frac{1}{n^s}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
definiert.
}{Eine
\definitionsverweis {Primzahl}{}{}
der Form
\mathl{2^n-1}{} heißt Mersennesche Primzahl.
}{Eine Sophie-Germain-Primzahl ist eine
\definitionsverweis {Primzahl}{}{}
$p$ mit der Eigenschaft, dass auch
\mathl{2p+1}{} eine Primzahl ist.
}
}
\inputaufgabepunkteloesung
{3}
{
Formuliere die folgenden Sätze. \aufzaehlungdrei{Der \stichwort {Chinesische Restsatz} {} für $\Z$.}{Das \stichwort {quadratische Reziprozitätsgesetz} {} für ungerade Primzahlen.}{Der \stichwort {Primzahlsatz} {.}}
}
{
\aufzaehlungdrei{Es sei $n$ eine positive natürliche Zahl mit kanonischer Primfaktorzerlegung
\mathl{n= p_1^{r_1} \cdot p_2^{r_2} { \cdots } p_k^{r_k}}{.} Dann induzieren die kanonischen Ringhomomorphismen
\maabb {} {\Z/(n)} {\Z/(p_i^{r_i} )
} {}
einen Ringisomorphismus
\mavergleichskettedisp
{\vergleichskette
{ \Z/(n)
}
{ \cong} { \Z/(p_1^{r_1} ) \times \Z/(p_2^{r_2} ) \times \cdots \times \Z/(p_k^{r_k} )
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}}{Es seien $p$ und $q$ zwei verschiedene ungerade
\definitionsverweis {Primzahlen}{}{.}
Dann gilt:
\mavergleichskettedisp
{\vergleichskette
{ \left( \frac{ p }{ q }\right) \cdot \left( \frac{ q }{ p }\right)
}
{ =} { (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2} }
}
{ =} { \begin{cases} -1 \, , \text{ wenn } p = q = 3 \mod 4 \, , \\ 1 \, , \text{ sonst} \, . \end{cases}
}
{ } {
}
{ } {
}
}
{}{}{}}{Es gilt die asymptotische Abschätzung
\mavergleichskettedisp
{\vergleichskette
{ \pi(x)
}
{ \sim} { \frac{x}{\ln (x)}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Das heißt
\mavergleichskettedisp
{\vergleichskette
{ \lim_{x \rightarrow \infty} \frac{\pi(x)}{ \frac{x}{\ln (x)} }
}
{ =} { \lim_{x \rightarrow \infty}\frac{\pi(x) \ln (x)}{x}
}
{ =} { 1
}
{ } {
}
{ } {
}
}
{}{}{.}}
}
\inputaufgabepunkteloesung
{2}
{
Bestätige die folgende Identität.
\mavergleichskettedisp
{\vergleichskette
{ 3^5 + 11^4
}
{ =} { 122^2
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}
{
Es ist
\mavergleichskettedisp
{\vergleichskette
{3^5
}
{ =} { 243
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und
\mavergleichskettedisp
{\vergleichskette
{11^4
}
{ =} { 121^2
}
{ =} {14641
}
{ } {
}
{ } {
}
}
{}{}{.}
Somit ist
\mavergleichskettedisp
{\vergleichskette
{3^5 + 11^4
}
{ =} { 243 +14641
}
{ =} { 14884
}
{ } {
}
{ } {
}
}
{}{}{.}
Andererseits ist auch
\mavergleichskettedisp
{\vergleichskette
{122^2
}
{ =} { 14884
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}
\inputaufgabepunkteloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabepunkteloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabepunkteloesung
{1}
{
Bestimme die
\definitionsverweis {Primfaktorzerlegung}{}{}
von
\mathdisp {\binom { 15 } { 5 }} { . }
}
{
Es ist
\mavergleichskettedisp
{\vergleichskette
{ \binom { 15 } { 5 }
}
{ =} { { \frac{ 15 \cdot 14 \cdot 13 \cdot 12 \cdot 11 }{ 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 } }
}
{ =} { { \frac{ 14 \cdot 13 \cdot 12 \cdot 11 }{ 4 \cdot 2 } }
}
{ =} { { \frac{ 7 \cdot 13 \cdot 3 \cdot 11 }{ 1 } }
}
{ =} { 3 \cdot 7 \cdot 11 \cdot 13
}
}
{}{}{.}
}
\inputaufgabepunkteloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabepunkteloesung
{4 (2+2)}
{
Zu einer positiven natürlichen Zahl $n$ sei $a_n$ das
\definitionsverweis {kleinste gemeinsame Vielfache}{}{}
der Zahlen
\mathl{1,2,3 , \ldots , n}{.}
\aufzaehlungzwei {Bestimme $a_n$ für
\mavergleichskette
{\vergleichskette
{ n
}
{ = }{ 1,2,3,4,5,6,7,8,9
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
} {Was ist die kleinste Zahl $n$ mit
\mavergleichskettedisp
{\vergleichskette
{a_n
}
{ =} {a_{n+1}
}
{ =} {a_{n+2}
}
{ =} {a_{n+3}
}
{ } {
}
}
{}{}{?}
}
}
{
\aufzaehlungzwei {Es ist
\mathdisp {a_1=1,\, a_2= 2,\, a_3=6,\, a_4=12,\, a_5=60,\, a_6=60,\, a_7=420,\, a_8=840,\, a_9=2520} { . }
} {Genau dann ist
\mavergleichskettedisp
{\vergleichskette
{a_{n+1}
}
{ >} { a_n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
wenn $n$ eine Primzahlpotenz
\mathbed {p^k} {}
{k \geq 1} {}
{} {} {} {,}
\zusatzklammer {$p$ Primzahl} {} {}
ist, da diese nicht als Faktor einer kleineren Zahl auftauchen. Man muss also nach der kleinsten Folge von drei Zahlen ohne Primzahlpotenzen suchen. Dies ist
\mathl{20,21,22}{,} die Antwort ist also $19$.
}
}
\inputaufgabepunkteloesung
{4}
{
Es seien \mathkor {} {x} {und} {y} {} natürliche Zahlen, die man beide als eine Summe von zwei Quadratzahlen darstellen kann. Zeige, dass man auch das Produkt $xy$ als Summe von zwei Quadratzahlen darstellen kann.
}
{
Es sei
\mavergleichskettedisp
{\vergleichskette
{x
}
{ =} {a^2 +b^2
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und
\mavergleichskettedisp
{\vergleichskette
{y
}
{ =} {c^2 +d^2
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Wir setzen
\mavergleichskettedisp
{\vergleichskette
{r
}
{ =} { ac -bd
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und
\mavergleichskettedisp
{\vergleichskette
{s
}
{ =} { ad+bc
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Dann ist
\mavergleichskettealign
{\vergleichskettealign
{ r^2 +s^2
}
{ =} { (ac-bd)^2 + (ad+bc)^2
}
{ =} { a^2c^2 +b^2d^2 -2acbd +a^2d^2+b^2c^2 +2adbc
}
{ =} { a^2c^2 +b^2d^2 +a^2d^2+b^2c^2
}
{ =} { (a^2 +b^2)( c^2 +d^2 )
}
}
{
\vergleichskettefortsetzungalign
{ =} { xy
}
{ } {}
{ } {}
{ } {}
}
{}{,}
also ist auch das Produkt eine Summe von zwei Quadratzahlen.
}
\inputaufgabepunkteloesung
{3}
{
Bestimme das inverse Element zu
\mathl{\overline{55}}{} in
\mathl{\Z/(93)}{.}
}
{
Der euklidische Algorithmus liefert
\mavergleichskettedisp
{\vergleichskette
{93
}
{ =} { 1 \cdot 55 + 38
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
\mavergleichskettedisp
{\vergleichskette
{ 55
}
{ =} { 1 \cdot 38 + 17
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
\mavergleichskettedisp
{\vergleichskette
{ 38
}
{ =} { 2 \cdot 17 +4
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
\mavergleichskettedisp
{\vergleichskette
{ 17
}
{ =} { 4 \cdot 4 +1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Somit ist
\mavergleichskettealign
{\vergleichskettealign
{ 1
}
{ =} { 17 - 4 \cdot 4
}
{ =} { 17- 4 \cdot ( 38 -2 \cdot 17 )
}
{ =} { 9 \cdot 17 - 4 \cdot 38
}
{ =} { 9 \cdot { \left( 55-38 \right) } - 4 \cdot 38
}
}
{
\vergleichskettefortsetzungalign
{ =} { 9 \cdot 55 -13 \cdot 38
}
{ =} { 9 \cdot 55 -13 \cdot { \left( 93-55 \right) }
}
{ =} { 22 \cdot 55 -13 \cdot 93
}
{ } {}
}
{}{.}
Daher ist
\mathdisp {22} { }
das inverse Element zu $55$ in
\mathl{\Z/(93)}{.}
}
\inputaufgabepunkteloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabepunkteloesung
{4}
{
Es sei
\mavergleichskette
{\vergleichskette
{ z
}
{ \in }{ \R
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
derart, dass es ein Polynom
\mavergleichskette
{\vergleichskette
{ P
}
{ \neq }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit rationalen Koeffizienten und mit
\mavergleichskettedisp
{\vergleichskette
{P(z)
}
{ =} {0
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gibt. Zeige, dass man
\mavergleichskettedisp
{\vergleichskette
{z
}
{ =} { { \frac{ u }{ v } }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
schreiben kann, wobei $v$ eine positive natürliche Zahl ist und es zu $u$ ein normiertes Polynom $Q$ mit ganzzahligen Koeffizienten und mit
\mavergleichskettedisp
{\vergleichskette
{Q(u)
}
{ =} {0
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gibt.
}
{
Es sei
\mavergleichskettedisp
{\vergleichskette
{P
}
{ =} { c_n X^n + \cdots + c_2X^2 +c_1X+c_0
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{c_i
}
{ = }{ { \frac{ a_i }{ b_i } }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
\mathl{a_i, b_i \in \Z}{,}
\mavergleichskette
{\vergleichskette
{b_i
}
{ > }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{c_n
}
{ \neq }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Wir multiplizieren dieses Polynom mit
\mathl{c_n^{-1}}{} und können somit annehmen, dass $P$ normiert ist.
Wir setzen
\mavergleichskettedisp
{\vergleichskette
{ b
}
{ =} { b_0b_1 \cdots b_{n-1}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Aus
\mavergleichskettedisp
{\vergleichskette
{P (z)
}
{ =} { z^n + c_{n-1}z^{n-1} + \cdots + c_2 z^2 +c_1z +c_0
}
{ =} { 0
}
{ } {
}
{ } {
}
}
{}{}{}
ergibt sich durch Multiplikation mit $b^n$ direkt
\mavergleichskettealign
{\vergleichskettealign
{0
}
{ =} { b^n { \left( z^n + c_{n-1}z^{n-1} + \cdots + c_2 z^2 +c_1z +c_0 \right) }
}
{ =} { b^nz^n + b^n c_{n-1}z^{n-1} + \cdots + b^n c_2 z^2 + b^nc_1z + b^nc_0
}
{ =} { b^nz^n + b c_{n-1} b^{n-1}z^{n-1} + \cdots + b^{n-2} c_2 b^2 z^2 + b^{n-1} c_1 b z + b^n c_0
}
{ =} { (bz)^n+ b c_{n-1} (bz)^{n-1} + \cdots + b^{n-2} c_2 ( bz)^2 + b^{n-1} c_1 (b z) + b^n c_0
}
}
{}
{}{.}
Dies bedeutet, dass
\mathl{bz}{} eine Nullstelle des Polynoms
\mavergleichskettedisp
{\vergleichskette
{ Q
}
{ =} { X^n+ b c_{n-1} X^{n-1} + \cdots + b^{n-2} c_2 X^2 + b^{n-1} c_1 X + b^n c_0
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ist. Dieses Polynom ist normiert und es besitzt wegen
\mavergleichskettedisp
{\vergleichskette
{ b^{n-i} c_i
}
{ =} { { \left( b_0 b_1 \cdots b_{n-1} \right) }^{n-i} { \frac{ a_i }{ b_i } }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ganzzahlige Koeffizienten. Somit ist
\mavergleichskettedisp
{\vergleichskette
{z
}
{ =} { { \frac{ bz }{ b } }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
mit
\mathl{b \in \N}{} und der Zähler
\mathl{bz}{} ist die Nullstelle eines normierten ganzzahligen Polynoms.
}
\inputaufgabepunkteloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabepunkteloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabepunkteloesung
{0}
{
}
{/Aufgabe/Lösung
}
\inputaufgabepunkteloesung
{0}
{
}
{/Aufgabe/Lösung
}