Prüfen, ob Abbildung injektiv, surjektiv und bijektiv ist

Question

Aufgabe:

Prüfen Sie, ob die folgende Abbildung surjektiv, injektiv oder bijektiv sind:

\( k: \mathbb{N} \to \mathbb{Z}/5\mathbb{Z}, \quad k(n) = [17^n]_5 \)

Kann mir jemand vielleicht einen Ansatz geben? Beispielsweise bei injektiv: Wie prüfe ich denn ob jedes \( y\in \mathbb{Z}/5\mathbb{Z} \) höchstens ein Urbild hat?

Answer 1

Setz doch mal ein paar Werte für n ein:

n=1: 17^1 mod 5 = 2, also \( k(1) = [2]_5 \)

n=2: 17^2 mod 5 = (17 mod 5)^2 mod 5 = 2^2 mod 5 = 4, also \( k(2) = [4]_5 \)

n=3: 17^3 mod 5 = 4*2 mod 5 = 3, \( k(3) = [3]_5 \)

n=4: 17^4 mod 5 = 3*2 mod 5 = 1, \( k(4) = [1]_5 \)

n=5: 17^5 mod 5 = 1*2 mod 5 = 2, \( k(5) = [2]_5 \), also nicht injektiv.

Im Allgemeinen kann eine Abbilung \( f : A \to B \) nur injektiv sein, wenn A weniger Elemente als B hat (d.h. \( \#A \le \#B\)). Es gibt unendlich viele natürliche Zahlen, aber nur 5 Restklassen modulo 5.

Erreicht die Funktion \( [0]_5 \)? Nein, denn \( 17^k \) ist niemals durch 5 teilbar, also gilt auch nie \( 17^k \mod 5 = 0 \). Deshalb ist sie auch nicht surjektiv

Comments

Das ist nachvollziehbar.

Wieso ist 17^3 mod 5 = 4*2 mod 5 = 3 ? Wie kommst du von 17^3 auf 4 * 2 ?

---

Du hast doch 17^2 mod 5 = 4 schon berechnet und 17 mod 5 = 2 kennst du auch, also:

17^3 mod 5 = (17^2 * 17) mod 5 = (17^2 mod 5)*(17 mod 5) mod 5 = 4*2 mod 5