Bestimme möglichst kleines x, sodass folgende Kongruenz vorliegt.

Question

ich suche eine möglichst kleine natürliche  Zahl x,sodass 7^{7^7} ≡ x mod 3 gilt.

Hat jemand eine Idee, wie ich dies machen könnte, ohne 7^7 auszurechnen?
Eventuell kleiner Fermat?

Answer 1

Es kommen ja nur 0 und 1 und 2 infrage.

0 kann es nicht sein, da 7er Potenzen nicht durch 3
teilbar sind, denn sonst müssten sie den Primfaktor 3

enthalten.

Aber weil 7 Ξ 1 mod 3 ist, sind auch alle

7er Potenzen  Ξ 1   mod  3, also ist das x=1.

Answer 2

Darfst du nicht gleich die Basis mod 3 nehmen ?

Comments

Das geht nur, weil 7 mod 3 = 1 ist,wie mathef bereits erwähnt hat.

Dass ich an sowas einfaches nicht gedacht habe :D

---

Du solltest ein paar MODULO Rechenregeln kennen:

(a ± b) MOD n = (a MOD n ± b MOD n) MOD n

(a * b) MOD n = (a MOD n * b MOD n) MOD n

Daraus folgt dann auch 

a^m MOD n = (a MOD n)^m MOD n

7^{7^7} MOD 3 = (7 MOD 3)^{7^7} MOD 3 = (1)^{7^7} MOD 3 = 1

---

Danke,  die kenne ich.  Hab mich aber irgendwie sehr auf den Fermat versteift, weil das in der Aufgabe mit als Hinweis stand.