Satz von Euler, doppelte exponenten


0

Guten Tag,

derzeit beschäftige ich mich mit dem Satz von Euler im modularen rechnen. Nun bin ich auf eine Aufgabe gestoßen, dessen Lösung ich nicht ganz verstehe.

nämlich: \((13^{13})^{13} mod 11\)

Mein Ansatz war: Zuerst 13*13 zu rechnen -> \(13^{169}\)

Nun folgt aus dem Satz von Euler (da 13 und 11 teilerfremd) dass \(13^{10}\) kongruent 1 modulo 11 ist.

Nun würde ich \(13^{169}\) schreiben als \((13^{10})^{16} *13^{9}\) 

\(13^{9}\) würde ich nun noch weiter zu \(2^{9}\) vereinfachen, was gleich 512 ergibt. 512 mod 11 ergäbe dann 6, nur ist das Ergebnis leider falsch. Kann mir einer meinen Fehler erklären und die richtigen Rechenschritte zeigen? Vielen Dank!

 

gefragt vor 2 Monate, 2 Wochen
s
sorbitwiezuckerersatz,
Student, Punkte: 34
 

6 ist nicht falsch.   -   maccheroni_konstante, verified kommentiert vor 2 Monate, 2 Wochen

in den Lösungen steht aber 8 mod 11, was ja 8 ergibt. Dort wurde 13^13 irgendwie mit modulo 10 reduziert, sodass am Ende nurnoch 2^3mod11 übrig bleibt.   -   sorbitwiezuckerersatz, kommentiert vor 2 Monate, 2 Wochen
Kommentar schreiben Diese Frage melden
2 Antworten
1

Hallo,

dann werden die in den Lösungen einen Fehler gemacht haben. Es macht schließlich auch keinen Sinn plötzlich mit modulo 10 weiter zu rechnen. 

Ich habe es auch nochmal nach gerechnet und es kommt auf jeden Fall 6 mod 11 als Lösung heraus. 

Grüße Christian

geantwortet vor 2 Monate, 1 Woche
christian strack, verified
Sonstiger Berufsstatus, Punkte: 14903
 

Danke für deine Antwort, ich glaube ich kann die Lösung doch nachvollziehen, habe einen Kommentar hinzugefügt und würde mich freuen, wenn du ihn dir angucken kannst um mir zu sagen, ob das so sinn macht. Vielen Dank :)   -   sorbitwiezuckerersatz, kommentiert vor 2 Monate, 1 Woche
Kommentar schreiben Diese Antwort melden
0

 

Nach intensivem Suchen bin ich dann doch auf die Lösung gekommen(?)

Nochmal zum Ansatz: Die Aufgabe ist \(13^{13^{13}} mod 11\). Da gilt \(ggt(13,11) = 1\) dürfen wir den Satz von Euler anwenden, der hier besagt: \(13^{\phi(11)} \equiv 1 mod 11\).

\(\phi(11)\) ist da 11 eine Primzahl ist durch \((11^{1-1})*(11-1) = 10\) gegeben.

Was sagt uns das bei unserem Beispiel? Das \(13^{10^{x}} \equiv 1 mod 11\). Genau hier setzten wir an und schauen uns zunächst den Exponenten \(13^{13} mod 10\) an, denn; Alles was bei dem Ausdruck \(13^{13}\) durch 10 Teilbar ist, ist ja Konkruent 1 mod 11, also interessieren wir uns vor allem an die Werte, die nicht kongruent 1 mod 11 sehen. Dass ist aber genau der Rest von \(13^{13} mod 10\).

\(13^{13} mod 10\) führt uns dann auf, wieder mit dem Satz von Euler (13 und 10 sind teilerfremd!): \(\phi(10) = \phi(2*5) = 4  \Rightarrow 13^{4} \equiv 1 mod 10\). Nun können wir \(13^{13} mod 10\) als \(13^{12 + 1} mod 10 = 13^{12}*13^1 mod 10\) wobei \(13^{12} \equiv 13^{4^3}  \equiv 1 mod 10\) ist.

Übrig beibt also noch \(13 mod 10 = 3\)

Für unsere eigentliche Aufgabe folgt daraus folgendes: \(13^{13^{13}}\) lässt sich als \(13^{10^{x}}*13^3\) schreiben, wobei x der Teil ist, der durch Ganzzahldivision mit 10 im Exponenten herauskommt. Dieser ist nach Euler kongruent 1, also hier nicht weiter von bedeutung. \(13^3)\ können wir (13-11) als \(2^3\) schreiben und kommen so auf: \(8 mod 11 = 8\)

 

geantwortet vor 2 Monate, 1 Woche
s
sorbitwiezuckerersatz,
Student, Punkte: 34
 

\((13^{13})^{13}\) ist nicht das gleiche wie \(13^{13^{13}}\)!   -   maccheroni_konstante, verified kommentiert vor 2 Monate, 1 Woche

Super, dann lag der Fehler ja darin, dass ich den Latexbefehl am Anfang nicht wusste. Danke! Macht die Rechung für \(13^{13^13}}\) Denn soweit Sinn? Vielen Dank!   -   sorbitwiezuckerersatz, kommentiert vor 2 Monate, 1 Woche

Wenn nach \( 13^{13^{13}} \) gefragt wird dann stimmt das :)
Ich denke du willst auch schreiben das \( 13^{12} \equiv (13^4)^3 \) gilt (Weil \( 13^{12} = 13^{3 \cdot 4} = (13^4)^3) \). Zumindest macht das im Kontext mehr Sinn oder irre ich mich?
Allerdings ist das nicht falsch was du schreibst, denn \( 13^{12} \equiv 13^{4^3} \mod(10) \) stimmt auch, es ist aber \( 13^{4^3} = 13^{64} \). Deshalb denke ich das hier auch Klammern vergessen wurden, es tut es mir aber Leid wenn ich gerade was übersehe, aber nochmal wie Maccheroni_Konstante bereits sagt ist es wichtig die Klammer richtig zu setzen, deshalb gehe ich hier nochmal darauf ein.

Grüße Christian
  -   christian strack, verified kommentiert vor 2 Monate, 1 Woche
Kommentar schreiben Diese Antwort melden