Question

Satz von Euler-Fermat funktioniert auch bei nicht teilerfremden Zahlen?

Ich habe die Anwendung des Satzes von Euler-Fermat soweit verstanden, jedoch wurde im Skript, das wir benutzen ein Beispiel genommen in dem a und n einen ggT<1 haben. Wieso funktioniert das?

Beispiel: 2313^(490) mod2310 = (2313^(480) * 2313^10) mod2310 = (3^10)mod2310 = 1299

2. Wie gesagt, denke ich, dass ich die Anwendung verstehe, aber die Definition des Satzes ist ja

a^(phi(n)) ≡ 1 mod n

könnte man das nicht auch missverstehen, weil 1 mod n ja immer 1 ist bei positiven Zahlen?

Also wie (a^(phi(n)) mod n = 1 mod n?

3. im letzten Schritt des Beispiels wurde die 2313 durch 3 ersetzt, ist das, weil 2313mod2310 = 3 ist? Geht das immer so?

Answer 1

. Wie gesagt, denke ich, dass ich die Anwendung verstehe, aber die Definition des Satzes ist ja
a^(phi(n)) ≡ 1 mod n
könnte man das nicht auch missverstehen, weil 1 mod n ja immer 1 ist bei positiven Zahlen?

Nein Dazu wird ja das Konkruenzsymbol ≡ und kein Gleichheitszeichen benutzt.

Dadurch weiß man das das mod sich auf beide Seiten der Kongruenz bezieht.

3. im letzten Schritt des Beispiels wurde die 2313 durch 3 ersetzt, ist das, weil 2313mod2310 = 3 ist? Geht das immer so?

richtig

a^n mod x = (a mod x)^n mod x

Man kann also immer den Modulo direkt auf die Basis anwenden.

Comments

Danke für deine Antwort!

Kannst du (oder ein anderer User) mir auch erklären, warum der Satz auch bei a und n funktioniert, wenn sie nicht teilerfremd sind?

---

Generell funktioniert der Satz nur, wenn a und n teilerfremd sind d.h. wenn ggT(a, n) = 1 gilt.

---

Wahrscheinlich habe ich irgendwo ein Brett vor dem Kopf. Ich verstehe den vorletzten Schritt noch nicht ganz, da hier a und n doch nicht teilerfremd sind. Warum können wir trotzdem Euler-Fermat anwenden?

---

Warum können wir trotzdem Euler-Fermat anwenden?

Wo wurde denn deiner Meinung nach der Satz von Euler/Fermat angewendet?

Ich glaube deine Schwierigkeiten liegen darin die Regeln auseinanderzuhalten die angewendet werden.