Wie würde man das berechnen?

Meine Idee wäre jetzt mit eulersche Phi Funktion, aber wie geht das?

LG

Answer 1

[aperfect10]

Für Module m > 0 gilt

wenn $a \equiv r_a \mod m\quad\text{und}\quad b \equiv r_b\mod m$ dann

$ab \equiv r_a r_b\mod m\quad\text{und}\quad a+b = r_a + r_b \mod m$ Damit kann man die Lösungen leicht von Hand ausrechnen.

Für die a) zum Beispiel:

$3^2 = 9 \equiv 2 \mod 7,$ also

$3^6 = 3^2\cdot3^2\cdot3^2 \equiv 2\cdot 2\cdot 2 \equiv 8 \equiv 1 \mod 7$ Oder bei der b):

$5^2 = 25 \equiv 4 \mod 7$ $5^6 = 5^2\cdot 5^2\cdot 5^2 \equiv 4\cdot 4\cdot 4 \equiv 64 \equiv 1 \mod 7$ Und Du hast recht, diese Gleichungen haben etwas mit der Phi-Funktion zu tun.

Schau Dir dazu den kleinen Satz von Fermat und den Satz von Euler an.

Viele Grüße!