Übungen

Übung 1

Sei p eine von 2 und 5 verschiedene Primzahl.

Übung 2

Zeigen Sie den Satz von Euler für den Spezialfall m = 11 und c = 4, indem Sie sich an der allgemeinen Beweisführung orientieren, die Berechnungen aber konkret durchführen.

Übung 3

Sei m ≥ 1, und sei a derart, dass a^φ(m) ≡  1 mod(m). Zeigen Sie, dass a teilerfremd zu m ist.

Übung 4

Lösen Sie die Kongruenzen

sowohl mit Hilfe der Lösungsformel als auch mit Hilfe des Euklidischen Algorithmus.

Übung 5

Beweisen Sie den allgemeinen Satz über die Lösung von Kongruenzen ersten Grades.

Übung 6

Bestimmen Sie mit Hilfe des allgemeines Satzes über die Lösung von Kongruenzen ersten Grades die Lösungen der folgenden Kongruenzen:

Übung 7

Zeigen oder widerlegen Sie:

Übung 8

Zeigen Sie mit Hilfe des Satzes von Fermat, dass 2⁹⁹ + 1 durch 57 teilbar ist.

Übung 9

Sei p prim, und sei x  ∈  ℤ derart, dass x² ≡  −1 (p). Zeigen Sie, dass p = 2 oder p ≡  1 (4).

[ Hinweis: Der Satz von Fermat ist hier hilfreich. ]

Übung 10

Sei p prim mit p ≠ und p ≡  1 (4). Zeigen Sie, dass es ein x  ∈  ℤ gibt mit

x² ≡  −1  (p).

[ Hinweis: Für jede Primzahl p gilt (vgl. die Übungen zum Abschnitt über Primzahlen):

(p − 1)!  ≡   −1 (p)(Satz von Wilson)

Ist also p > 2, so gilt für q = (p − 1)/2, dass

∏_{1 ≤ i ≤ q} i (p − i)  ≡   −1  (p).

Verwenden Sie dieses Ergebnis, um die Aussage zu beweisen. ]

Übung 11

Wir hatten gesehen, dass der Satz von Fermat äquivalent ist zur folgenden Aussage:

Sei p prim. Dann gilt a^p ≡  a (p) für alle a.

Es stellt sich die Frage, ob wir den Satz von Euler ebenfalls ohne die Voraussetzung der Teilerfremdheit formulieren können. Wir betrachten also die folgende Aussage:

(+)  Sei m ≥ 1. Dann gilt a^{φ(m) + 1} ≡  a (m) für alle a.