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).

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).

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).

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})^{×}.

Abgabe: am Donnerstag, den 8.12. (in der Vorlesung, oder bei Herrn Martin).