7. Übung Elementare Algorithmen in der Algebra

Priv. Doz. Dr. G. Nebe (SS 00)

Aufgabe 24. Zeigen Sie, dass 2^{x} + 1 zusammengesetzt ist, falls x keine 2-Potenz ist. Zeigen Sie, dass für a ≥ 2 die Zahl a^{n} −1 zusammengesetzt ist, falls entweder a ≠ 2 oder n keine Primzahl ist.

Aufgabe 25. Zeigen Sie, dass für zusammengesetztes ungerades N die Anzahl der a ∈ (ℤ/Nℤ)^{∗}, für die N eine Pseudoprimzahl zur Basis a ist, ≤ \frac{1}{2}φ(N) ist.

Aufgabe 26. Zeigen Sie, dass endliche Untergruppen der multiplikativen Gruppe eines Körpers zyklisch sind. Insbesondere sind die Einheitengruppen endlicher Körper zyklisch.

Aufgabe 27. Beweisen Sie Satz (6.26): Sei N ungerade, N +1 = ∏_{j=1}^{n} q_{j}^{β_{j}} ·R mit paarweise verschiedenen Primzahlen q_{j} und q_{j}| R̸ (j = 1, …, n) R < \sqrt{N}. Gibt es D ∈ ℕ mit ggT (D, N) = 1 und für alle j = 1, …, n Zahlen α_{j} ∈ ℤ/Nℤ[\sqrt{D}]^{∗} so dass für die Lucas Folge U^{(j)} zu α_{j} gilt:

ggT (U_{(N+1)/q_{j}}^{(j)}, N) = 1, U_{N+1}^{(j)} ≡ 0 (mod N)

so ist N eine Primzahl.

Aufgabe 28. Berechnen Sie die folgenden Legendre Symbole:

(\frac{246}{257}) , (\frac{240}{499}) , (\frac{1234}{257}) .

Abgabe: Donnerstag, den 8.6.00, in der Übung 12:30 Uhr im kl. physik. Hörsaal