Eigenschaften der Kongruenz Modulo 5

Question

Aufgabe (Kongruenz modulo).

Für $x, y \in \mathbb{Z}$ gelte genau dann $x \equiv_{5} y$, wenn es ein $p \in \mathbb{Z}$ mit $x=5 p+y$ gibt.

(a) Zeigen Sie, dass $\equiv_{5}$ eine Äquivalenzrelation auf $\mathbb{Z}$ ist.

(b) Zeigen Sie: Für $x, y \in \mathbb{Z}$ gilt genau dann $x \equiv_{5} y$, wenn $5 \mid x-y$ gilt.

(c) Zeigen Sie: Für $x, \tilde{x}, y, \tilde{y} \in \mathbb{Z}$ mit $x \equiv_{5} \tilde{x}$ und $y \equiv_{5} \tilde{y}$ gilt auch $x+y \equiv_{5} \tilde{x}+\tilde{y}$ und $x y \equiv_{5} \tilde{x} \tilde{y}$.

(d) Bestimmen Sie $\mathbb{Z} / \equiv_{5}$. Wieviele Elemente hat der Quotient?

(e) Es seien eine Menge $X$ und eine Äquivalenzrelation $c$ auf $X$ gegeben. Eine Transversale von $X$ bzgl. $c$ ist eine Teilmenge $T$ von $X$ so, dass es für jedes $K \in X / c$ genau ein $t \in T$ mit $K=[t]_{c}$ gibt. Geben Sie zwei Transversalen von $\mathbb{Z}$ bzgl. $\equiv_{5}$ an.

(f) Zeigen Sie durch Induktion: Für alle $n \in \mathbb{N}$ ist $3^{4 n-1} \equiv_{5} 2$.

Answer 1

zu (c)

es geht hier nur darum, die Definitionen einzusetzen

x≡x' => x=5p+x', y≡y' => y=5p'+x'

x+y=5p+x'+5p'+x'=5(p+p')+(x'+y')  mit r:=p+p'∈ℤ => x+y≡x'+y'

Multiplikation analog

zu (d)

Hier sollen nur alle Äquivalenzklassen dargestellt werden, also alle x, für die gilt x≡y sollen zusammengefasst werden, diese sind konkret [0], [1], [2], [3], [4] oder durch entsprechende Repräsentanten dargestellt