Mathematik online lernen im Mathe-Forum. Nachhilfe online
Startseite » Forum » Wie löse ich die Aufgaben mit dem Satz von Euler?

Wie löse ich die Aufgaben mit dem Satz von Euler?

Universität / Fachhochschule

Primzahlen

Teilbarkeit

Tags: chinesischer Restsatz, eulersche Phi-Funktion, modulo, Primzahl, Teilbarkeit

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
einstein42

einstein42 aktiv_icon

23:55 Uhr, 18.08.2019

Antworten
Hallo Leute!

Ich habe folgende Aufgaben bekommen, die ich ich ohne Taschenrechner lösen soll:

2(232)mod11

14(20192019)mod60

Ich weiß, dass ich ähnlich wie in diesem Video: www.youtube.com/watch?v=-J3P9pzL4sY

den Satz von Euler anwenden muss.

Leider verstehe ich nicht, wie ich mit den doppelten Exponenten am besten umgehen soll. Könnt ihr mir da weiterhelfen?

Danke!

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich bräuchte bitte einen kompletten Lösungsweg." (setzt voraus, dass der Fragesteller alle seine Lösungsversuche zur Frage hinzufügt und sich aktiv an der Problemlösung beteiligt.)
Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:
 
Online-Nachhilfe in Mathematik
Antwort
michaL

michaL aktiv_icon

07:23 Uhr, 19.08.2019

Antworten
Hallo,

> Leider verstehe ich nicht, wie ich mit den doppelten Exponenten am besten umgehen soll.
"Schritt"weise. Erst den "inneren" Exponenten mit dem Satz von Euler-Fermat verkleinern, dann den "äußeren.

Mfg Michael
Antwort
ermanus

ermanus aktiv_icon

09:43 Uhr, 19.08.2019

Antworten
Hallo,
Vorsicht Falle!
232 muss ja modulo 10 gerechnet werden, d.h. bei der "inneren"
Rechnung (232) kann man den Satz von Euler-Fermat nicht verwenden,
da 2 und 10 nicht teilerfremd sind.
Gruß ermanus
Antwort
HAL9000

HAL9000

10:23 Uhr, 19.08.2019

Antworten
Bei der zweiten Aufgabe geht es sogar ganz ohne Euler-Fermat: Es ist

1420192019(-1)20192019-1 mod 15

und außerdem gilt trivialerweise 14201920190 mod 4 ... muss man jetzt nur kombinieren (Chinesischer Restsatz).

-------------------------------------------------------------

Für zusammengesetzte Module m ist übrigens der Einsatz der de.wikipedia.org/wiki/Carmichael-Funktion oft effizienter als der der Eulerschen φ-Funktion: Für teilerfremde a,m ist nämlich für aras mod m bereits das Bestehen der Kongruenz rs mod λ(m) hinreichend, was eine geringere Forderung als rs mod φ(m) ist.

Antwort
ermanus

ermanus aktiv_icon

12:57 Uhr, 19.08.2019

Antworten
@HAL9000: Danke für den Tipp mit der Carmichael-Funktion.
Gruß ermanus
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.