Kurs:Zahlentheorie (Osnabrück 2025)/Arbeitsblatt 4/latex
\setcounter{section}{4}
\zwischenueberschrift{Übungsaufgaben}
\inputaufgabe
{}
{
Bestimme alle Lösungen der linearen Kongruenz
\mavergleichskette
{\vergleichskette
{ 12x
}
{ = }{ 3 \mod 21
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
{} {}
\inputaufgabe
{}
{
Bestimme alle Lösungen der linearen Kongruenz
\mavergleichskette
{\vergleichskette
{ 13x
}
{ = }{ 11 \mod 141
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
{} {}
\inputaufgabe
{}
{
Berechne die Restklasse von
\mathl{2^{1563}}{} modulo $23$.
}
{} {}
\inputaufgabegibtloesung
{}
{
Berechne
\mathl{3^{1457}}{} in
\mathl{{\mathbb Z}/(13)}{.}
}
{} {}
\inputaufgabe
{}
{
Charakterisiere diejenigen positiven ungeraden Zahlen $n$ mit der Eigenschaft, dass bei dem in Aufgabe 1.26 beschriebenen Algorithmus genau zwei ungerade Zahlen auftreten \zusatzklammer {nämlich $n$ und $1$, aber beliebig viele gerade Zahlen} {} {.}
}
{} {}
\inputaufgabe
{}
{
Es sei $p$ eine
\definitionsverweis {Primzahl}{}{.}
Beweise durch Induktion den
kleinen Fermat,
also die Aussage, dass
\mathl{a^p -a}{} ein Vielfaches von $p$ für jede ganze Zahl $a$ ist.
}
{} {}
\inputaufgabe
{}
{
Bestimme den Rest von $27!$ modulo $31$.
}
{} {}
\inputaufgabe
{}
{
Bestimme die Zerlegung von
\mathl{X^{p-1}-1}{} in
\definitionsverweis {irreduzible Polynome}{}{}
im Polynomring
\mathl{\Z/(p)[X]}{.} Beweise aus dieser Zerlegung
den Satz von Wilson.
}
{} {}
\inputaufgabegibtloesung
{}
{
Es seien
\mavergleichskette
{\vergleichskette
{ a,b
}
{ \geq }{ 2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und sei
\mavergleichskette
{\vergleichskette
{ n
}
{ = }{ ab
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
\aufzaehlungdreiabc{Zeige, dass die beiden Polynome $X^a-1$ und $X^b-1$ Teiler des Polynoms $X^n-1$ sind.
}{Es sei
\mavergleichskette
{\vergleichskette
{ a
}
{ \neq }{ b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Ist $(X^a-1)(X^b-1)$ stets ein Teiler von $X^n-1$?
}{Man gebe drei Primfaktoren von $2^{30} -1$ an.
}
}
{} {}
\inputaufgabegibtloesung
{}
{
\aufzaehlungdreiabc{Finde mit Hilfe des euklidischen Algorithmus eine Darstellung der $1$ für die beiden Zahlen $19$ und $109$.
}{Nach dem Chinesischen Restsatz haben wir die Isomorphie
\mavergleichskettedisp
{\vergleichskette
{ \Z/(2071)
}
{ \cong} { \Z/(19) \times \Z/(109)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Welche Restklasse modulo $2071$ entspricht dem Restklassenpaar $(1 ,0)$ und welche dem Paar $( 0,1 )$?
}{Bestimme diejenige Restklasse modulo $2071$, die modulo $19$ den Rest $5$ hat und die modulo $109$ den Rest $10$ hat.
}
}
{} {}
\inputaufgabegibtloesung
{}
{
\aufzaehlungzweiabc{Bestimme für die Zahlen $3$, $11$ und $13$ modulare Basislösungen, finde also die kleinsten positiven Zahlen, die in
\mathdisp {\Z/( 3 ) \times \Z/(11) \times \Z/(13)} { }
die Restetupel
$(1,0,0),\, (0,1,0)$ und $(0,0,1)$
repräsentieren.
}{Finde mit den Basislösungen die kleinste positive Lösung $x$ der simultanen Kongruenzen
\mathdisp {x = 2 \!\! \mod 3 , \, \, \, \, x = 5 \!\! \mod 11 \text{ und } x = 6 \!\! \mod 13} { . }
}
}
{} {}
\inputaufgabegibtloesung
{}
{
\aufzaehlungzweiabc{Bestimme für die Zahlen $2$, $9$ und $25$ modulare Basislösungen, finde also die kleinsten positiven Zahlen, die in
\mathdisp {\Z/( 2 ) \times \Z/( 9 ) \times \Z/(25)} { }
die Restetupel
$(1,0,0),\, (0,1,0)$ und $(0,0,1)$
repräsentieren.
}{Finde mit den Basislösungen die kleinste positive Lösung $x$ der simultanen Kongruenzen
\mathdisp {x = 0 \!\! \mod 2 , \, \, \, \, x = 3 \!\! \mod 9 \text{ und } x = 5 \!\! \mod 25} { . }
}
}
{} {}
\inputaufgabe
{}
{
\aufzaehlungzweiabc{Bestimme für die Zahlen $4$, $5$ und $11$ modulare Basislösungen, finde also die kleinsten positiven Zahlen, die in
\mathdisp {\Z/( 4 ) \times \Z/( 5 ) \times \Z/(11)} { }
die Restetupel
$(1,0,0),\, (0,1,0)$ und $(0,0,1)$
repräsentieren.
}{Finde mit den Basislösungen die kleinste positive Lösung $x$ der simultanen Kongruenzen
\mathdisp {x = 3 \!\! \mod 4 , \, \, \, \, x = 2 \!\! \mod 5 \text{ und } x = 10 \!\! \mod 11} { . }
}
}
{} {}
\inputaufgabegibtloesung
{}
{
Man berechne in $\Z/(80)$ die Elemente \aufzaehlungdreiabc{ $3^{1234567}$, }{ $2^{1234567}$, }{ $5^{1234567}$. }
}
{} {}
\inputaufgabe
{}
{
Es seien $R$ und
\mathl{S_1 , \ldots , S_n}{}
\definitionsverweis {kommutative Ringe}{}{}
mit dem
\definitionsverweis {Produktring}{}{}
\mavergleichskettedisp
{\vergleichskette
{S
}
{ =} {S_1 \times \cdots \times S_n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Zeige, dass ein
\definitionsverweis {Ringhomomorphismus}{}{}
\maabbdisp {\varphi} { R } { S
} {}
dasselbe ist wie eine Familie von Ringhomomorphismen
\maabbdisp {\varphi_i} { R } { S_i
} {}
für
\mavergleichskette
{\vergleichskette
{ i
}
{ = }{ 1 , \ldots , n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
{} {}
\inputaufgabegibtloesung
{}
{
Man gebe eine surjektive Abbildung \maabbdisp {\varphi} {\Z} { \Z/( 3 ) } {} an, die mit der Multiplikation verträglich \zusatzklammer {also ein Monoidhomomorphismus} {} {} ist, aber kein \definitionsverweis {Ringhomomorphismus}{}{} ist.
}
{} {}
\inputaufgabegibtloesung
{}
{
Es sei $n$ eine positive natürliche Zahl mit der Faktorzerlegung
\mavergleichskettedisp
{\vergleichskette
{ n
}
{ =} { 2^r \cdot 5^s \cdot d
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
wobei $d$ zu $n$ teilerfremd sei
\zusatzklammer {
\mavergleichskette
{\vergleichskette
{ r,s
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{ d
}
{ = }{ 1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
sind erlaubt} {} {.}
Zeige, dass die Periodenlänge der Dezimalentwicklung von
\mathl{{ \frac{ 1 }{ n } }}{} gleich der multiplikativen Ordnung von $10$ in $\Z/( d )$ ist.
}
{} {}
\inputaufgabe
{}
{
Es sei $R$ ein
\definitionsverweis {kommutativer Ring}{}{,}
der einen
\definitionsverweis {Körper}{}{}
der positiven
\definitionsverweis {Charakteristik}{}{}
\mavergleichskette
{\vergleichskette
{p
}
{ > }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
enthalte
\zusatzklammer {dabei ist $p$ eine Primzahl} {} {.}
Zeige, dass die Abbildung
\maabbeledisp {} { R } { R
} { f } {f^p
} {,}
ein
\definitionsverweis {Ringhomomorphismus}{}{}
ist, den man den \stichwort {Frobeniushomomorphismus} {} nennt.
}
{} {Tipp: Benutze
Aufgabe 3.22.}
\inputaufgabegibtloesung
{}
{
Es sei $p$ eine Primzahl und sei
\mathl{f(x)}{} ein Polynom mit Koeffizienten in
\mathl{\Z/( p )}{} vom Grad
\mavergleichskette
{\vergleichskette
{ d
}
{ \geq }{ p
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Zeige, dass es ein Polynom $g(x)$ mit einem Grad $< p$ derart gibt, dass für alle Elemente
\mavergleichskette
{\vergleichskette
{ a
}
{ \in }{ \Z/( p )
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Gleichheit
\mavergleichskettedisp
{\vergleichskette
{ f(a)
}
{ =} { g(a)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gilt.
}
{} {}
\inputaufgabe
{}
{
Zeige, dass eine \definitionsverweis {Untergruppe}{}{} einer \definitionsverweis {zyklischen Gruppe}{}{} wieder zyklisch ist.
}
{} {}
\inputaufgabe
{}
{
Zeige, dass eine \definitionsverweis {Restklassengruppe}{}{} einer \definitionsverweis {zyklischen Gruppe}{}{} wieder zyklisch ist.
}
{} {}
\inputaufgabe
{}
{
Es sei
\mavergleichskettedisp
{\vergleichskette
{G
}
{ =} { H_1 \times \cdots \times H_n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
die
\definitionsverweis {Produktgruppe}{}{}
der endlichen Gruppen
\mathl{H_1 , \ldots , H_n}{.} Zeige die folgenden Aussagen.
\aufzaehlungzwei {
\mavergleichskettedisp
{\vergleichskette
{ \exp G
}
{ =} {
\operatorname{kgV} ( \exp H_i , i = 1 , \ldots , n )
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
} { $G$ ist genau dann
\definitionsverweis {zyklisch}{}{,}
wenn alle $H_i$ zyklisch sind und wenn deren Ordnungen paarweise
\definitionsverweis {teilerfremd}{}{}
sind.
}
}
{} {}
\inputaufgabe
{}
{
Es seien $n_1, \ldots , n_k$ positive natürliche Zahlen und es sei
\mavergleichskettedisp
{\vergleichskette
{ G
}
{ =} { \Z/(n_1 ) \times \Z/(n_2 ) \times \cdots \times \Z/(n_k )
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
die
\definitionsverweis {Produktgruppe}{}{.
Bestimme den
\definitionsverweis {Exponenten}{}{}
von $G$.}
}
{} {}
\inputaufgabegibtloesung
{}
{
Wir betrachten die endliche Permutationsgruppe $S_n$ zu einer Menge mit $n$ Elementen. \aufzaehlungzweiabc{Zeige, dass es in $S_n$ Elemente der \definitionsverweis {Ordnung}{}{} $n$ gibt. }{ Man gebe ein Beispiel für eine Permutationsgruppe $S_n$ und einem Element darin, dessen Ordnung größer als $n$ ist. }
}
{} {}
\inputaufgabegibtloesung
{}
{
Zeige, dass es in der
\definitionsverweis {Restklassengruppe}{}{}
\mathl{\Q/\Z}{} zu jedem
\mavergleichskette
{\vergleichskette
{ n
}
{ \in }{ \N_+
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
Elemente gibt, deren
\definitionsverweis {Ordnung}{}{}
gleich $n$ ist.
}
{} {}
\inputaufgabe
{}
{
Für eine \definitionsverweis {Gruppe}{}{} $G$ bezeichne $T(G)$ die Menge aller Elemente mit endlicher \definitionsverweis {Ordnung}{}{} in $G$. Zeige folgende Aussagen. \aufzaehlungdrei{Ist $G$ abelsch, so ist $T(G)$ eine \definitionsverweis {Untergruppe}{}{} von $G$. }{Ist $T(G)$ eine Untergruppe, so ist $T(G)$ ein \definitionsverweis {Normalteiler}{}{} in $G$. }{Es gibt eine Gruppe $G$, für die $T(G)$ keine Untergruppe von $G$ ist. }
}
{} {}
\zwischenueberschrift{Aufgaben zum Abgeben}
\inputaufgabe
{3}
{
Formuliere und beweise
\zusatzklammer {bekannte} {} {}
Teilbarkeitskriterien für Zahlen im Dezimalsystem für die Teiler
\mavergleichskette
{\vergleichskette
{ k
}
{ = }{ 2,3,5,9,11
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
{} {}
\inputaufgabe
{4}
{
Es sei $p$ eine ungerade Primzahl. Beweise unter Verwendung
des Satzes von Wilson,
dass
\mavergleichskettedisp
{\vergleichskette
{ 1^2 \cdot 3^2 \cdot 5^2 \cdots (p-4)^2 \cdot (p-2)^2
}
{ =} { (-1)^{\frac{p+1}{2} } \mod p
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gilt.
}
{} {}
\inputaufgabe
{3}
{
Es sei
\mavergleichskette
{\vergleichskette
{ f(x)
}
{ = }{ x^7+2x^3 +3x+4
}
{ \in }{ { \left( \Z/( 5 ) \right) } [x]
}
{ }{
}
{ }{
}
}
{}{}{.}
Finde ein Polynom
\mavergleichskette
{\vergleichskette
{ g(x)
}
{ \in }{ { \left( \Z/( 5 ) \right) } [x]
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
vom Grad $< 5$, das für alle Elemente aus
\mathl{\Z/( 5 )}{} mit
\mathl{f(x)}{} übereinstimmt.
}
{} {}
\inputaufgabe
{3}
{
\aufzaehlungzweiabc{Bestimme für die Zahlen $2$, $3$ und $7$ modulare Basislösungen, finde also die kleinsten positiven Zahlen, die in
\mathdisp {\Z/( 2 ) \times \Z/( 3 ) \times \Z/( 7 )} { }
die Restetupel
$(1,0,0),\, (0,1,0)$ und $(0,0,1)$
repräsentieren.
}{Finde mit den Basislösungen die kleinste positive Lösung $x$ der simultanen Kongruenzen
\mathdisp {x = 1 \!\! \mod 2 , \, \, \, \, x = 2 \!\! \mod 3 \text{ und } x = 2 \!\! \mod 7} { . }
}
}
{} {}