WS 05/06 Priv.-Doz. Dr. S. Wewers

Algebra I

6. Übungsblatt

Aufgabe 1: (1+2=3 P) Sei n ∈ ℕ und n = n_{1} · . . . · n_{r} eine Zerlegung von n in paarweise teilerfremde Faktoren. Setze m_{i} := n/n_{i}.

(a) Zeigen Sie: Für jedes i gibt es eine natürliche Zahl y_{i} ∈ {1, …, n − 1} mit y_{i}m_{i} ≡ 1 (mod n_{i}). Weiterhin gilt: sind x_{1}, …, x_{r} ∈ ℤ beliebige ganze Zahlen, so ist

x := ∑_{i=1}^{r} x_{i}y_{i}m_{i}

eine Lösung der simultanen Kongruenzen x ≡ x_{i} (mod n_{i}), i = 1, …, r.

(b) Bestimmen Sie die eindeutige ganze Zahl x ∈ {0, …, 104} mit

x ≡ 1 (mod 3)
x ≡ 2 (mod 5)
x ≡ 3 (mod 7)

Verwenden Sie dazu Teil (a).

Lösung:

(a) Wir setzen n ≥ 2 voraus.

• Im Falle n_{i} = 1 setze man y_{i} := 1. Es sei nun n_{i} ≥ 2 vorausgesetzt. Nach Voraussetzung sind die Zahlen n_{i} und m_{i} = n_{1} · . . . · n_{i−1} · n_{i+1} · . . . · n_{r} teilerfremd. Also gibt es nach dem Euklidischen Algorithmus Zahlen a, b ∈ ℤ derart, daß 1 = an_{i} + bm_{i}. Es sei y_{i} ≡ b mod n_{i} so gewählt, daß y_{i} ∈ {0, …, n − 1}. Es folgt

y_{i}m_{i} ≡ bm_{i} = 1 − an_{i} ≡ 1 mod n_{i} .

Insbesondere ist y_{i} ≠ 0. Damit ist der erste Teil der Behauptung gezeigt.

• Betrachtet man x modulo n_{j}, so ergibt sich wegen m_{i} ≡ 0 mod n_{j} für j ≠ i und aufgrund der Wahl der y_{j} demnach

x ≡ x_{j}y_{j}m_{j} ≡ x_{j} mod n_{j}

für j = 1, …, r.

• Wir wollen zusatzlich noch beweisen, daß obige Lösung eindeutig modulo n ist, d.h. daß jede weitere Lösung x′ der simultanen Kongruenzen x′ ≡ x_{i} mod n_{i}, i = 1, …, r, notwendigerweise x′ ≡ x mod n erfüllen muß. Dazu beachte man, daß y := x − x′ erfüllt

y ≡ 0 mod n_{i}

für i = 1, …, r. Also sind n_{1}, …, n_{r} jeweils Teiler von y. Da die Zahlen n_{1}, …, n_{r} paarweise teilerfremd sind, folgt daraus, daß auch deren Produkt n := n_{1} · . . . · n_{r} ein Teiler von y = x − x′ ist. Daraus folgt definitionsgemäß x′ ≡ x mod n.

(b) Der Euklidische Algorithmus liefert

1 = 12 · 3 − 1 · 35 = −4 · 5 + 1 · 21 = −2 · 7 + 1 · 15 .

Also haben wir

2 · 35 ≡ 1 mod 3
1 · 21 ≡ 1 mod 5
1 · 15 ≡ 1 mod 7 .

Nach Teil (a) ist die eindeutige Lösung modulo 105 gegeben durch 1 · 2 · 35 + 2 · 1 · 21 + 3 · 1 · 15 = 157 ≡ 52 mod 105 .

Aufgabe 2: (3 P) Sei G eine endliche zyklische Gruppe der Ordnung n und g ein Erzeuger von G. Sei h ∈ G ein beliebiges Element. Der diskrete Logarithmus von h zur Basis g ist die (eindeutige) Zahl x = log_{g}(h) ∈ {0, …, n − 1} mit h = g^{x}.

Sei n = n_{1} · . . . · n_{r} eine Zerlegung von n in teilerfremde Faktoren. Setze m_{i} := n/n_{i}, g_{i} := g^{m_{i}} und h_{i} := h^{m_{i}}. Zeigen Sie:

(a) Das Element g_{i} ∈ G hat die Ordnung n_{i}.

(b) Die Ordnung von h_{i} ist ein Teiler von n_{i}.

(c) Es gibt eindeutige Zahlen x_{i} ∈ {0, …, n_{i} − 1} mit h_{i} = g_{i}^{x_{i}}, i = 1, …, r.

(d) Sei x ∈ {0, …, n − 1} die eindeutige Lösung der simultanen Kongruenzen x ≡ x_{i} (mod n_{i}). Dann gilt h = g^{x}, d.h. x = log_{g}(h).

Lösung:

(a) Für x ∈ ℤ gilt g_{i}^{x} = g^{xn/n_{i}}, und wegen ord g = n folgt

1 = g_{i}^{x} ⟺ xn/n_{i} ≡ 0 mod n ⟺ n_{i}|x .

Daher ist ord g_{i} = n_{i}.

(b) Es gilt

h_{i}^{n_{i}} = h^{m_{i}n_{i}} = h^{n} = 1 ,

denn n = |G|. Daher ist die Ordnung von h_{i} ein Teiler von n_{i}.

(c) Es sei y := log_{g}(h), d.h. es gelte h = g^{y}. Es sei x_{i} ∈ {0, …, n_{i} − 1} derart,

daß x_{i} ≡ y mod n_{i}. Dann gilt wegen ord g_{i} = n_{i} folglich

g_{i}^{x_{i}} = g_{i}^{y} = g^{m_{i}y} = h^{m_{i}} = h_{i} .

Wegen ord g_{i} = n_{i} ist dieses x_{i} auch eindeutig bestimmt.

(d) Nach dem Beweis zu Teil (c) war x_{i} ≡ y mod n_{i}, wobei y = log_{g}(h). Nach der Wahl von x gilt also x ≡ y mod n_{i} für i = i, …, r. Aufgrund der Eindeutigkeit von x folgt daraus x = y.

Aufgabe 3: (1+2=3 P)

(a) Zeigen Sie, dass 3 eine Primitivwurzel modulo 31 ist.

(b) Bestimmen Sie den diskreten Logarithmus von 2 modulo 31 zur Basis 3, d.h. die eindeutige Zahl x ∈ {0, …, 29} mit

3^{x} ≡ 2 (mod 31).

Benutzen Sie dazu das in Aufgabe 2 angegebene Verfahren (mit G := (ℤ/ℤ · 31)^{×}, g := 3 und h := 2).

Lösung:

(a) Die Ordnung von \overline{3} in (ℤ/31ℤ)^{×} ist ein Teiler von φ(31) = 30, d.h. sie ist eine der Zahlen 1, 2, 3, 5, 6, 10, 15, 30. Wir müssen also lediglich nachprüfen, daß 3^{n} ≢ 1 mod 31 gilt für n = 2, 3, 5, 6, 10, 15. Wir berechnen

3^{2}  ≡ 9 mod 31
3^{3} ≡ 3 · 3^{2}  ≡ −4 mod 31
3^{5} ≡ 3^{2} · 3^{3} ≡ 9 · (−4) ≡ −36 ≡ −5 mod 31
3^{6} ≡ (3^{3})^{2} ≡ (−4)^{2}  ≡ 16 mod 31
3^{10} ≡ (3^{5})^{2} ≡ (−5)^{2}  ≡ −6 mod 31
3^{15} ≡ 3^{5} · 3^{10} ≡ (−5) · (−6)  ≡ −1 mod 31 .

Daher gilt ord \overline{31} = 30 in (ℤ/31ℤ)^{×}.

(b) Wir berechnen zunächst

2^{5}  ≡ 1 mod 31
2^{6}  ≡ 2 mod 31
2^{10} ≡ 1^{2} ≡ 1 mod 31
2^{15} ≡ 1^{3} ≡ 1 mod 31

Also ergibt sich folgendes Tableau.

\begin{matrix}i & n_{i} & m_{i} & g_{i} & h_{i} & x_{i} \\ 1 & 2 & 15 & \overline{3}^{15} = \overline{−1} & \overline{2}^{15} = \overline{1} & 0 \\ 2 & 3 & 10 & \overline{3}^{10} = \overline{−6} & \overline{2}^{10} = \overline{1} & 0 \\ 3 & 5 & 6 & \overline{3}^{6} = \overline{16} & \overline{2}^{6} = \overline{2} & x_{3} \end{matrix}

Um x_{3} zu berechnen, brauchen wir folgende Nebenrechnungen

\begin{aligned}g_{3}^{2} & = & \overline{3}^{12} = \overline{3}^{2} · \overline{3}^{10} = \overline{9} · \overline{−6} = \overline{−54} & = & \overline{8} \\ g_{3}^{3} & = & \overline{3}^{18} = \overline{3}^{1}5 · \overline{3}^{3} = \overline{−1} · \overline{−4} & = & \overline{4} \\ g_{3}^{4} & = & \overline{3}^{24} = (\overline{3}^{12})^{2} = \overline{8}^{2} = \overline{64} & = & \overline{2} . \end{aligned}

Demnach ergibt sich x_{1} = x_{2} = 0 und x_{3} = 4. Die gesuchte Zahl x ist also Lösung der simultanen Kongruenzen

x ≡ 0 mod 2
x ≡ 0 mod 3
x ≡ 4 mod 5 .

Dieses hat die Lösung x = 24. (Bemerkung: Wir hatten in obiger Rechnung bereits \overline{3}^{24} = \overline{2} herausgefunden und wären damit fertig gewesen. Das war aber nur ein glücklicher Zufall.)

Aufgabe 4: (3 P) Sei r ≥ 2 eine ganze Zahl. Zeigen Sie:

(a) Es gilt die Kongruenz

5^{2^{r−2}} ≡ 1 (mod 2^{r})

und, falls r ≥ 3,

5^{2^{r−3}} ≢ 1 (mod 2^{r}).

Hinweis: Schreibe 5 = 1 + 4 und benutze die Binomialentwicklung und Induktion nach r.

(b) Sind x, y ∈ ℤ ganze Zahlen mit

(−1)^{x} · 5^{y} ≡ 1 (mod 2^{r}),

so gilt x ≡ 0 (mod 2) und y ≡ 0 (mod 2^{r−2}).

(c) Die Abbildung (x, y) ↦ (−1)^{x} · 5^{y} definiert einen Isomorphismus

ℤ/ℤ · 2 × ℤ/ℤ · 2^{r−2} ≅ (ℤ/ℤ · 2^{r})^{×}.

Lösung:

(a) Wir wollen durch Induktion nach r ≥ 2 folgende Aussage beweisen.

5^{2^{r−2}} ≡ 1 + 2^{r} mod 2^{r+1} .

Für r = 2 stimmt die Aussage offenbar. Im Induktionsschritt nehmen wir an, die Aussage stimme für ein r ≥ 2. Also gibt es ein k ∈ ℤ derart, daß 5^{2^{r−2}} = 1 + 2^{r} + k · 2^{r+1}. Es folgt

5^{2^{r−1}} = (5^{2^{r−2}})^{2} = (1 + (1 + 2k)2^{r})^{2}
= 1 + (1 + 2k)2^{r+1} + (1 + 2k)^{2}2^{2r}
= 1 + 2^{r+1} + (k + (1 + 2k)^{2}2^{r−2})2^{r+2}
≡ 1 + 2^{r+1} mod 2^{r+2} .

Also ist obige Behauptung bewiesen. Insbesondere folgt daraus

5^{2^{r−2}} ≡ 1 + 2^{r} ≡ 1 mod 2^{r} ,

da eine Kongruenz mod 2^{r+1} stets auch eine Kongruenz mod 2^{r} nach sich zieht. Im Falle r ≥ 3 gilt

5^{2^{r−3}} ≡ 1 + 2^{r−1} ≢ 1 mod 2^{r} ,

da 2^{r−1} ≢ 0 mod 2^{r} gilt.

Zusatz: Aus dem hier Bewiesenen folgt

ord \overline{5} = 2^{r−2} in (ℤ/2^{r}ℤ)^{×} .

Denn wegen \overline{5}^{2^{r−2}} = \overline{1} ist die Ordnung t := ord \overline{5} ein Teiler von 2^{r−2}, d.h. es gilt t = 2^{s} für ein s ∈ {0, …, r − 2}. Es kann aber nicht s ≤ r − 3 gelten, da

sonst \overline{5}^{2^{r−3}} = (\overline{5}^{2^{s}})^{2^{r−3−s}} = \overline{1} wäre, im Widerspruch zur zweiten Aussage der Aufgabestellung.

(b) Wir nehmen x, y ≥ 0 an. Es gilt 5^{y} = (1 + 4)^{y} ≡ 1 mod 4. Andererseits gilt

nach Voraussetzung

(−1)^{x}5^{y} ≡ 1 mod 4 ,

da 4 ein Teiler von 2^{r} ist. Daraus folgt x ≡ 0 mod 2, denn es gilt −1 ≢ 1 mod 4. Die Voraussetzung besagt also

5^{y} ≡ 1 mod 2^{r} ,

d.h.

\overline{5}^{y} = \overline{1}

in (ℤ/2^{r}ℤ)^{×}. Nach Teil (a) ist die Ordnung von \overline{5} in (ℤ/2^{r}ℤ)^{×} gleich 2^{r−2}. Daraus folgt, daß 2^{r−2} ein Teiler von y ist, d.h. es gilt y ≡ 0 mod 2^{r−2}.

(c) Wir betrachten die Abbildung

\begin{matrix}φ : (ℤ/2ℤ) × (ℤ/2^{r−2}ℤ) & → & (ℤ/2^{r}ℤ)^{×} , \\ (\overline{x}, \overline{y}) & ↦ & \overline{−1}^{x} · \overline{5}^{y} . \end{matrix}

Wegen ord \overline{−1} = 2 und ord \overline{5} = 2^{r−2} in (ℤ/2^{r}ℤ)^{×} ist die Abbildung wohldefiniert. Man rechnet leicht nach, daß sie ein Gruppenhomomorphismus ist. Nach Teil (b) ist sie injektiv. Ferner haben beide Gruppen je 2^{r−1} Elemente. Also ist φ ein Gruppenisomorphismus.