| Autor |
  Modulo großer Zahlen |
|
tetriscyphervalo
Wenig Aktiv 
Dabei seit: 19.01.2021
Mitteilungen: 39
 |  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 
Dabei seit: 02.09.2017
Mitteilungen: 2270
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 
Dabei seit: 04.10.2013
Mitteilungen: 1793
 | Beitrag No.2, eingetragen 2021-10-03
|
Profil
|
tetriscyphervalo
Wenig Aktiv 
Dabei seit: 19.01.2021
Mitteilungen: 39
| Beitrag No.3, vom Themenstarter, eingetragen 2021-10-03
|
Nice, werde mich diesbezüglich einlesen 👍
|
Profil
|
Kuestenkind
Senior
Dabei seit: 12.04.2016
Mitteilungen: 2430
| 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
Dabei seit: 19.01.2013
Mitteilungen: 7855
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
Wenig Aktiv
Dabei seit: 19.01.2021
Mitteilungen: 39
| 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
Dabei seit: 12.04.2016
Mitteilungen: 2430
| 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
Wenig Aktiv
Dabei seit: 19.01.2021
Mitteilungen: 39
| 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
Dabei seit: 04.10.2013
Mitteilungen: 1793
| 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
Dabei seit: 12.04.2016
Mitteilungen: 2430
| 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
Dabei seit: 12.04.2016
Mitteilungen: 2430
| 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
Wenig Aktiv
Dabei seit: 19.01.2021
Mitteilungen: 39
| 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
Dabei seit: 12.04.2016
Mitteilungen: 2430
| 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
Wenig Aktiv
Dabei seit: 19.01.2021
Mitteilungen: 39
| 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
Dabei seit: 12.04.2016
Mitteilungen: 2430
| 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
Dabei seit: 02.09.2017
Mitteilungen: 2270
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
Wenig Aktiv
Dabei seit: 19.01.2021
Mitteilungen: 39
| 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
Dabei seit: 04.10.2013
Mitteilungen: 1793
| 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
Wenig Aktiv
Dabei seit: 19.01.2021
Mitteilungen: 39
| 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
Dabei seit: 12.04.2016
Mitteilungen: 2430
| 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
Dabei seit: 04.10.2013
Mitteilungen: 1793
| 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
Wenig Aktiv
Dabei seit: 19.01.2021
Mitteilungen: 39
| 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
Dabei seit: 12.04.2016
Mitteilungen: 2430
| 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
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
