Matroids Matheplanet Forum Index
Moderiert von Wauzi
Teilbarkeit » Kongruenzen » Modulo großer Zahlen
Autor
Universität/Hochschule J Modulo großer Zahlen
tetriscyphervalo
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2021
Mitteilungen: 38
  Themenstart: 2021-10-03

Gegeben sei: $7^{7^{7}} \pmod 9$ Wie kann ich dies ohne Taschenrechner berechnen? Kann mir jemand vlt. ein kleines Rechenbeispiel geben? Danke


   Profil
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 2069
Wohnort: Thüringen
  Beitrag No.1, eingetragen 2021-10-03

Bei sowas bieten sich immer die Potenzgesetze an. 7^7^7 = 7^(7^7)=7^823543 Nun, 7^3 MOD 9 = (7-9)^3 MOD 9 = 1 Wenn also 7^3 MOD 9 = 1 ist, dann ist auch 7^6, 7^9... auch 1 Folglich auch 823542 , da 823542 MOD 3 = 0 ist. Übrig bleibt dann 7^1 MOD 9 = 7 Lösung unter vorbehalt.


   Profil
Kezer
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.10.2013
Mitteilungen: 1573
  Beitrag No.2, eingetragen 2021-10-03

Kennst du den Satz von Euler-Fermat? [Die Antwort wurde vor Beitrag No.1 begonnen.]


   Profil
tetriscyphervalo
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2021
Mitteilungen: 38
  Beitrag No.3, vom Themenstarter, eingetragen 2021-10-03

Nice, werde mich diesbezüglich einlesen 👍


   Profil
Kuestenkind
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 12.04.2016
Mitteilungen: 2186
  Beitrag No.4, eingetragen 2021-10-03

Huhu tetriscyphervalo, Darij berechnet hier \(7^{7^{7}} \pmod {10}\) auf Seite 457. Vll hilft das ja auch nochmal als Beispiel. Gruß, Küstenkind


   Profil
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 7311
Wohnort: Milchstraße
  Beitrag No.5, eingetragen 2021-10-03

\quoteon(2021-10-03 12:44 - pzktupel in Beitrag No. 1) 7^7^7 = 7^(7^7)=7^823543 \quoteoff Gib zu: Hast du das ohne TR gerechnet? 🙃


   Profil
tetriscyphervalo
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2021
Mitteilungen: 38
  Beitrag No.6, vom Themenstarter, eingetragen 2021-10-03

Habe die Aufgabe so gelöst, dass ich die innere Klammer mit dem Satz von Euler-Fermat berechnet habe, dann den zweiten Teil modularer Exponentiation. Nochmals Danke an euch 👌


   Profil
Kuestenkind
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 12.04.2016
Mitteilungen: 2186
  Beitrag No.7, eingetragen 2021-10-03

Huhu tetriscyphervalo, was meinst du mit "innere Klammer" und "zweiten Teil"? Das verstehe ich gerade nicht wirklich. Gruß, Küstenkind


   Profil
tetriscyphervalo
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2021
Mitteilungen: 38
  Beitrag No.8, vom Themenstarter, eingetragen 2021-10-03

Ja, schlecht erklärt von mir. Also wir haben die Zahl $7^{7^{7}}=7^{(7^{7})}$ Als 1. betrachte ich die nur die Klammer: $7^7 \pmod 9$. Mit dem Satz von Euler-Fermat kommt als Ergebnis $7$ raus. Als nächstes betrachte ich also $7^7$, da beim 1. Ergebnis $7$ raus kam, kann man direkt die Lösung aus dem 1. Schritt nehmen und man ist fertig. Bei $11^{11^{11}}$ bekomme ich beim 1. Schritt $5$ raus. Also ist der nächste Schritt $11^5$. Mit modularer Exponentiation kommt $5$ raus. Ich habe versucht den 2. Schritt mit Hilfe d. Satzes von Euler-Fermat zu lösen, allerdings kam ich hier nicht weiter: $11^5 \equiv 11^{6\cdot 1-1} \equiv (11^6)^1\cdot 11^{-1} \equiv 1^1\cdot 11^-1 \pmod 9$. Hier verwirrt mich die $-1$ beim Exponenten von $11$. Deswegen haben ich den 2. Schritt mit der modularen Exponentiation berechnet und kam auf das Endergebnis $5$. Vlt. geht es ja, nur ich komme nicht drauf 🤔 Liebe Gruße


   Profil
Kezer
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.10.2013
Mitteilungen: 1573
  Beitrag No.9, eingetragen 2021-10-03

\(\begingroup\)\(\newcommand{\Q}{\mathbb{Q}} \newcommand{\N}{\mathbb{N}} \newcommand{\R}{\mathbb{R}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\CC}{\mathbb{C}} \newcommand{\C}{\mathscr{C}} \newcommand{\A}{\mathbb A} \newcommand{\PP}{\mathbb{P}} \newcommand{\LL}{\mathcal{L}} \newcommand{\OO}{\mathcal{O}} \newcommand{\FF}{\mathcal{F}} \newcommand{\variety}{\mathcal{V}} \newcommand{\Spec}{\operatorname{Spec}} \newcommand{\Gal}{\operatorname{Gal}} \newcommand{\sep}{\mathrm{sep}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\Ab}{\mathbf{Ab}} \newcommand{\Set}{\mathbf{Set}} \newcommand{\Coh}{\mathbf{Coh}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\Bl}{\operatorname{Bl}} \newcommand*\dd{\mathop{}\!\mathrm{d}}\) \quoteon(2021-10-03 16:48 - tetriscyphervalo in Beitrag No. 8) Ja, schlecht erklärt von mir. \quoteoff Das ist nicht das Problem. Ich vermute mal Kuestenkind hat schon erahnen können, was du meintest. Das Problem ist, dass dein Ansatz falsch ist und nur per Zufall funktioniert hat. Du darfst nicht einfach den Exponenten modulo $9$ rechnen. Hier hat es nur zum richtigen Ergebnis geführt, da zufällig $7^7 \equiv 1 \pmod 9$ gilt.\(\endgroup\)


   Profil
Kuestenkind
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 12.04.2016
Mitteilungen: 2186
  Beitrag No.10, eingetragen 2021-10-03

Huhu tetriscyphervalo, wieso kannst du denn einfach den Modulo in den Exponenten ziehen? Wenn es um \(2^{10} \mod 9\) geht ist dieses doch auch nicht \(2^1=2\), da \(10\equiv 1 \mod 9\) ist. Es ist doch \(2^{10}=1024\equiv 7 \mod 9\). Gruß, Küstenkind [Die Antwort wurde nach Beitrag No.8 begonnen.]


   Profil
Kuestenkind
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 12.04.2016
Mitteilungen: 2186
  Beitrag No.11, eingetragen 2021-10-03

\quoteon(2021-10-03 17:07 - Kezer in Beitrag No. 9) Das ist nicht das Problem. Ich vermute mal Kuestenkind hat schon erahnen können, was du meintest. \quoteoff Ich hatte es befürchtet - ja :) Gruß, Küstenkind


   Profil
tetriscyphervalo
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2021
Mitteilungen: 38
  Beitrag No.12, vom Themenstarter, eingetragen 2021-10-03

Dann steh ich jetzt auf dem Schlauch. Habe jetzt drei Aufgaben mit der Methode berechnet, 2 von der Klausur und alle ergeben Zufällig die richtige Antwort. Was wäre der richtige Ansatz? Danke


   Profil
Kuestenkind
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 12.04.2016
Mitteilungen: 2186
  Beitrag No.13, eingetragen 2021-10-03

Schau dir doch nochmal das Beispiel von Darij an. Ich kann dir das sonst auch nochmal an dem Beispiel \(11^{11^{11}}\mod 9\) zeigen: Zunächst stellen wir fest, dass \(11\) und \(9\) tellerfremd sind. Es ist \(\phi(9)=6\) und somit \(11^6 \equiv 1 \mod 9\). Somit wollen wir schreiben: \(11^{11^{11}}=11^{6a+b}=(11^6)^a \cdot 11^b\equiv 11^b \pmod 9\) Um das \(b\) zu bestimmen rechnen wir nun also \(11^{11} \mod 6\). Es ist \(\phi(6)=2\) und damit: \(11^{11}=11^{5\cdot 2+1}=(11^2)^5\cdot 11^1\equiv 11\equiv 5 \pmod 6\) Somit geht es nun noch um \(11^5\equiv 2^5=32\equiv 5 \pmod 9\). Gruß, Küstenkind


   Profil
tetriscyphervalo
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2021
Mitteilungen: 38
  Beitrag No.14, vom Themenstarter, eingetragen 2021-10-03

Danke dir, habe mir das Beispiel aus dem Buch angeschaut, allerdings nur den Anfang verstanden gehabt. Das $\%$ im Buch hat mich aus dem Konzept geworfen. Vielen Dank 🙃


   Profil
Kuestenkind
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 12.04.2016
Mitteilungen: 2186
  Beitrag No.15, eingetragen 2021-10-03

Wenn du nochmal üben möchtest, könntest du ja einmal \(8^{{15}^{21}} \mod 15\) bestimmen. Dir noch einen schönen Abend. Gruß, Küstenkind


   Profil
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 2069
Wohnort: Thüringen
  Beitrag No.16, eingetragen 2021-10-03

\quoteon(2021-10-03 20:03 - Kuestenkind in Beitrag No. 15) Wenn du nochmal üben möchtest, könntest du ja einmal \(8^{{15}^{21}} \mod 15\) bestimmen. Dir noch einen schönen Abend. Gruß, Küstenkind \quoteoff Eine schöne Übungsaufgabe. Es ist eben sehr fieß, Aufgaben wie a^a^a mod b zu stellen. Der Schüler weiß eben nicht sofort ob a^(a^a) MOD b oder (a^a)^a MOD b zu rechnen ist. Und in der Klausur kommt dann a^b^c MOD d.


   Profil
tetriscyphervalo
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2021
Mitteilungen: 38
  Beitrag No.17, vom Themenstarter, eingetragen 2021-10-04

$\varphi(15)=8$, mit Eulers Theorem haben wir $8^8\equiv 1 \pmod{15}$ $\Rightarrow 8^{15^{21}}=8^{8\cdot m+n}=(8^8)^m\cdot 8^n\equiv 1^m\cdot 8^n \pmod {15} \equiv 8^n \pmod{15}$ Um $n$ zu bestimmen, berechnen wir $15^{21}\pmod{8}$ $\varphi(8)=4$ Eulers Theorem: $15^4\equiv 1\pmod 8$ $15^{21}\equiv 15^{4\cdot 5+1}\equiv (15^4)^5 \cdot 15^1\equiv 7\pmod 8$ $\Rightarrow 8^7\equiv 8^4 \cdot 8^3 \pmod{15} \equiv 8^3 \pmod{15} \equiv 2\pmod{15}$ Ist der Rechenweg korrekt? Gruß [Die Antwort wurde nach Beitrag No.15 begonnen.]


   Profil
Kezer
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.10.2013
Mitteilungen: 1573
  Beitrag No.18, eingetragen 2021-10-04

\(\begingroup\)\(\newcommand{\Q}{\mathbb{Q}} \newcommand{\N}{\mathbb{N}} \newcommand{\R}{\mathbb{R}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\CC}{\mathbb{C}} \newcommand{\C}{\mathscr{C}} \newcommand{\A}{\mathbb A} \newcommand{\PP}{\mathbb{P}} \newcommand{\LL}{\mathcal{L}} \newcommand{\OO}{\mathcal{O}} \newcommand{\FF}{\mathcal{F}} \newcommand{\variety}{\mathcal{V}} \newcommand{\Spec}{\operatorname{Spec}} \newcommand{\Gal}{\operatorname{Gal}} \newcommand{\sep}{\mathrm{sep}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\Ab}{\mathbf{Ab}} \newcommand{\Set}{\mathbf{Set}} \newcommand{\Coh}{\mathbf{Coh}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\Bl}{\operatorname{Bl}} \newcommand*\dd{\mathop{}\!\mathrm{d}}\) Der Rechenweg ist OK. Der Stil ist allerdings ausbaufähig. Du solltest mehr vollständige deutsche Sätze schreiben, definieren was $m,n$ sind, begründen wieso du Euler-Fermat anwenden darfst und kurz erklären, dass du $8^4 \equiv 1 \pmod{15}$ schriftlich ausgerechnet hast.\(\endgroup\)


   Profil
tetriscyphervalo
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2021
Mitteilungen: 38
  Beitrag No.19, vom Themenstarter, eingetragen 2021-10-04

\quoteon(2021-10-04 11:26 - Kezer in Beitrag No. 18) Der Rechenweg ist OK. Der Stil ist allerdings ausbaufähig. Du solltest mehr vollständige deutsche Sätze schreiben, definieren was $m,n$ sind, begründen wieso du Euler-Fermat anwenden darfst und kurz erklären, dass du $8^4 \equiv 1 \pmod{15}$ schriftlich ausgerechnet hast. \quoteoff Danke für die Tipps. Habe natürlich bei mir auf dem Blatt geschrieben, dass der $ggT(8,15)=1$ ist und ich somit Euler-Fermat benutzen kann. In den Vorlesungsfolien haben sie $n,m$ nicht definiert. Das einzige was ich weiß ist, dass $n$ kleinst möglich sein muss. Weiß nicht als was ich sie definieren kann. Bei $8^4\equiv 1 \pmod {15}$ meinst du den letzten Rechenweg, mit $8^4 \cdot 8^3$ oder?


   Profil
Kuestenkind
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 12.04.2016
Mitteilungen: 2186
  Beitrag No.20, eingetragen 2021-10-04

Huhu, das mag zum Teil ja auch etwas an mir liegen - ich habe in #13 auch keine Musterlösung für eine Klausur aufgeschrieben (da der Weg identisch zum Skript ist - und dort alles ausführlich erklärt und aufgeschrieben wird). In einer Kette reicht das modulo auch einfach am Ende. Statt \(8^7\equiv 8^4 \cdot 8^3 \pmod{15} \equiv 8^3 \pmod{15} \equiv 2\pmod{15}\) kannst du z. B. schreiben: \(8^7=8^2\cdot 8^2 \cdot 8^2 \cdot 8\equiv 4\cdot 4 \cdot 4 \cdot 8 \equiv 4\cdot 8 =32 \equiv 2\pmod{15}\) Das erleichtert den Lesefluss und erklärt auch gleich deine Rechnung. Es freut mich aber, dass du dich noch mit meiner Aufgabe beschäftigt hast! Gruß, Küstenkind @Kezer: Happy Birthday! :) [Die Antwort wurde nach Beitrag No.18 begonnen.]


   Profil
Kezer
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.10.2013
Mitteilungen: 1573
  Beitrag No.21, eingetragen 2021-10-04

\(\begingroup\)\(\newcommand{\Q}{\mathbb{Q}} \newcommand{\N}{\mathbb{N}} \newcommand{\R}{\mathbb{R}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\CC}{\mathbb{C}} \newcommand{\C}{\mathscr{C}} \newcommand{\A}{\mathbb A} \newcommand{\PP}{\mathbb{P}} \newcommand{\LL}{\mathcal{L}} \newcommand{\OO}{\mathcal{O}} \newcommand{\FF}{\mathcal{F}} \newcommand{\variety}{\mathcal{V}} \newcommand{\Spec}{\operatorname{Spec}} \newcommand{\Gal}{\operatorname{Gal}} \newcommand{\sep}{\mathrm{sep}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\Ab}{\mathbf{Ab}} \newcommand{\Set}{\mathbf{Set}} \newcommand{\Coh}{\mathbf{Coh}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\Bl}{\operatorname{Bl}} \newcommand*\dd{\mathop{}\!\mathrm{d}}\) \quoteon(2021-10-04 11:39 - tetriscyphervalo in Beitrag No. 19) In den Vorlesungsfolien haben sie $n,m$ nicht definiert. Das einzige was ich weiß ist, dass $n$ kleinst möglich sein muss. Weiß nicht als was ich sie definieren kann. \quoteoff Du benutzt bloß Division mit Rest, d.h. es gibt für alle $z \in \Z$ gibt es ganze Zahlen $m,n \in \Z$ mit $z = 8m + n$ (und man kann $|n| < 8$ wählen). Ich meinte bloß, dass du schreiben sollst, dann $m,n$ ganze Zahlen sind, sodass $15^{21} = 8m+n$ gilt - man kann ja nicht einfach beliebig undefinierte Symbole verwenden. \quoteon(2021-10-04 11:39 - tetriscyphervalo in Beitrag No. 19) Bei $8^4\equiv 1 \pmod {15}$ meinst du den letzten Rechenweg, mit $8^4 \cdot 8^3$ oder? \quoteoff Ja, einfach kurz hinschreiben, woher $8^4 \equiv 1 \pmod{15}$ kommt. Sowas wie "man rechnet per Hand nach, dass $8^4 \equiv 1 \pmod{15}$ reicht schon, aber zumindest sollte man das erwähnen. [Die Antwort wurde nach Beitrag No.19 begonnen.]\(\endgroup\)


   Profil
tetriscyphervalo
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2021
Mitteilungen: 38
  Beitrag No.22, vom Themenstarter, eingetragen 2021-10-04

Danke danke für die Tipps und Hilfe. \quoteon(2021-10-04 11:45 - Kuestenkind in Beitrag No. 20) Es freut mich aber, dass du dich noch mit meiner Aufgabe beschäftigt hast! [Die Antwort wurde nach Beitrag No.18 begonnen.] \quoteoff Na bin ja hier um zu lernen. Mich freut es eher, dass hier so aktiv geholfen wird 🙂 Gruß


   Profil
Kuestenkind
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 12.04.2016
Mitteilungen: 2186
  Beitrag No.23, eingetragen 2021-10-04

Gerne! Eine (letzte) Anmerkung bzw. Alternative noch von mir: Du kannst auch \(8^7=8^{8-1}=8^8\cdot 8^{-1}\) schreiben und ausnutzen, dass du ja schon festgestellt hast, dass \(8^8\equiv 1 \pmod {15}\). Dieses schreibe ich auch eigentlich nur, weil du ja geschrieben hast: \quoteon(2021-10-03 16:48 - tetriscyphervalo in Beitrag No. 8) Hier verwirrt mich die $-1$ beim Exponenten von $11$. \quoteoff Und dieses sollte dich eigentlich nicht verwirren, da es einfach bedeutet, dass man das Inverse nimmt. In diesen Beispiel ist eben \(8\cdot 2=1\) - und schon bist du fertig. Die Existenz des Inversen ist hier gesichert, da 8 und 15 relativ prim sind. In deinem anderen Beispiel ist dann eben \(11\cdot 5=1\). Allgemein nutzt man für das Finden von Inversen den erweiterten euklidischen Algorithmus. Heutzutage gibt es im Netz natürlich auch Rechner, die das erledigen. Gruß, Küstenkind


   Profil
tetriscyphervalo hat die Antworten auf ihre/seine Frage gesehen.
tetriscyphervalo hat selbst das Ok-Häkchen gesetzt.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]