Question

Bestimmen Sie 2²⁰¹⁴ mod 2017.

Naja, schwierig auszumultiplizieren...

Danke.

Answer 1

Die Standardmethode ist square-and-multiply https://de.wikipedia.org/wiki/Bin%C3%A4re_Exponentiation Hier geht's aber schneller: 2017 ist prim, mit dem kleinen Satz von Fermat ist: $$2^{2014}=2^{2016-2}=2^{-2} \mod 2017 $$ Inversenbestiimung im Restkalssenring standardmäßig über den erw. Euk https://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmusl.Alg: Aber auch das geht hier schneller: Es ist $$2^{-1}=1009 \mod 2017$$ Damit $$2^{2014}=1009^2=1018081 \equiv 1513 \mod 2917$$

Comments

ich denke ein eindeutiger Rechenweg sollte es schon sein.

Mindestens damit ich es für mich selbst notiert habe und es auch nachvollziehen kann.

Eine Lösung, die ich nicht begreife, bringt mir ja auch wenig..

Das von Anonym kann ich auch nicht nachvollziehen..

Daher schaue ich noch weiter :)

---

Was ist denn daran nicht eindeutig? Was ist überhaupt eine eindeutige Rechnung?

---

ich glaube, da muss so eine ähnliche Rechnung hin

https://www.mathelounge.de/6724/aufgabe-berechnen-sie-211-103-mod-101

das ähnelt vom Aufbau her dem Beispiel oben mit der Iteration

Aber wenn die Lösung so stimmt, ist doch gut :)

---

Kann man sagen

2^{-1} = 1009 mod 2017

Weil
2^{-1} * 2 = 2018 = 2017+1  = 1 mod 2017?

---

Soweit so gut.

der Rechner im link liegt falsch?

http://www.am.hs-mannheim.de/KryptoLern/potenzieren.php?basis=2&exponent=2014&modulus=2017

 

Die Inversenbestimmung kann ich auch nicht nachvollziehen.

Und dann ist da noch das Ding, dass 2^-2 nicht Element von {0,1,2,...2016} ist.

---

Wenn man was ausrechnet ist es egal wie man das tut, Hauptsache die Rechnung (d.h. die Rechenschritte) sind richtig. Und dann nimmt man gerne die kürzeste Rechnung.

---

okay, kannst du mir sagen, wie man auf die 1009 kommt?

---

und ist 2^-2 enthalten in {0,1,2,....,2016}?

ist doch keine ganze zahl.

---

Ich habe mal eine Frage zu dem Lösungsweg.

Wie kommst du auf \(2^{2016-2}\equiv 2^{-2}\mod 2017\)?

Es ist ja \(2^{2016-2}=2^{2016}\cdot 2^{-2}.\) Aber wie geht es dann weiter? Wieso fällt da \(2^{2016}\) weg?

---

@Lu, genauso ist es. @anonym, der Andere: Siehe Lu das ist im Restklassenring mod 2017 Ich hab das Inverse auch nicht bestimmt sondern schlicht "gesehen" (wobei das hier nicht schwierig ist.) Wir rechnen hier in einem Körper und da kann man durch nicht null-Elemente dividieren, d.h. die Zahl existiert.

---

Es ist verdammt schwierig hier auf mehrere Leute gleichzeitig zu antworten. @...Nick... Das ist der kleine Satz von Fermat wie im Post angemerkt. 2017 ist prim. @Anonym: Richtig, 2^-2 ist keine ganze Zahl. Wir haben hier aber auch keine ganzen zahlen sondern Restklassen, d.h. Äquivalenzklassen von Zahlen mit der entsprechenden Addition/Multiplikation/Potentiation

---

Abgedrehter Scheiß muss ich hier mal anmerken.

@nick. nach fermat gilt  : a^p-1 mod p =1   p prim, wenn ggt(a,p)=1, beim prim trivial wenn a ungleich p.

2²⁰¹⁶mod2017 =1 ,  da 2017 prim, wird also zu 1.

---

Also dann nehmen wir jetzt 2^-2 als Lösung an.

Kann man die Inverse tatsächlich so bestimmen?

---

@Anonym: Natürlich kann man das so machen, sonst würd ich das doch nicht schreiben. Dann bleibt die Frage wie sehr man irgendwem aus dem internet trauen kann...

---

muss nicht auch 2^-2 *1513 mod 2017 = 1 sein? ist doch sonst keine inverse...

---

war nicht bös gemeint, ist nur fast zu einfach :D

---

2^-2 ist 1513 mod 2017. Das iNverse dazu ist natürlich 2^2=4.

---

Wir sind hier bei mindestens drei verschiedenen Anonyms. Das ist extrem unübersichtlich.

---

Also: 2^2014 = 2^-2 mod 2017 

Da 1 mod 2017 = 2017 + 1 = 2018 = 1 = 2⁰ = 2^-1 * 2 = 1009

Und da 2^-2 = (2^-1)² folgt 2²⁰¹⁴ = 2^-2 = 1009² = 1018081 = 1513 mod2017

---

Die zweite Zeile ist Unsinn. DIe andern beiden sind richtig.

---

Stimmt.

2⁰ = 1

2⁰ / 2 = 2^-1 = 2018 / 2 = 1009

und dann weiter.

Schönen Abend.

Answer 2

Also ich habe das gerade im Rechner eingegeben und kann dir sagen, dass das Ergebnis lautet:

2²⁰¹⁴ mod 2017 = 1513

 

Aber wie ich den Rechenweg erstelle, verstehe ich selbst leider nicht..

Comments

Mit dem Taschenrechner?

---

Vielleicht damit: https://www.wolframalpha.com/input/?i=+2%5E2014+mod+2017

---

nicht im normalen Taschenrechner. ich habe das auf der Seite berechnet:

http://www.am.hs-mannheim.de/KryptoLern/potenzieren.php?basis=2&exponent=2014&modulus=2017


Ich versuche das gerade anhand einiger Seiten zu verstehen..

Bin gerade auf: http://www.austromath.at/medienvielfalt/materialien/krypto/lernpfad/content/k_euler.htm

Ich kritzle auch schon verzweifelt auf meinem Block, aber ich glaube, ich hab gleich einen Anfang.

---

also, hab auch nochmal nachgesucht:

wenn gilt ggt(a,p)=1,  dann ist:   a^p-1 mod p = 1 , p prim

damit ergibt sich 2²⁰¹⁴mod2017 = 2²⁰¹⁶ * 2^-2  mod2017 = 2²⁰¹⁶mod2017 * 2^-2mod2017

= 1 * 2^-2mod2017 = 0,25.

Stimmt aber nicht mit dem Ergebnis von dir und vom link überein? Fehler gemacht?

---

also ich bin jetzt mal auf der seite

http://matheplanet.com/default3.html?call=viewtopic.php?topic=159656&ref=http%3A%2F%2Fwww.google.de%2Furl%3Fsa%3Dt%26rct%3Dj%26q%3D%26esrc%3Ds%26source%3Dweb%26cd%3D1%26ved%3D0CDEQFjAA

 

Bei 2^12543 mod 15: folgendes geschrieben.

Wenn man gar keinen anderen Plan hat, kann man damit auch Potenzen mit großen Exponenten knacken
2^12543 == (2^4181)^3 == (2^4096*2^64*2^16*2^4*2^1)^3 mod 15

Ich komme gerade nicht auf φ(n)..

hast du das vielleicht?

Das, was ich mir bisher notiert habe ist nach:

http://www.matheboard.de/archive/404135/thread.html

Demnach habe ich:

2²⁰¹⁴ mod 2017

= 2 * 2²⁰¹³ mod 2017

= 2 * (2³)⁶⁷¹ mod 2017

Aber das ist wohl auch nicht ganz richtig..

---

Auf der Seite, die du angegeben hast, rechnest du ja die schnelle Methode vor. Da du dasselbe Resultat hast, wie WolframAlpha, stimmt das wohl. Hast du dies selbst programmiert? (Kreuzchen bei ausführlich zeigt die vollständige Rechnung.)

http://www.am.hs-mannheim.de/KryptoLern/potenzieren.php?basis=2&exponent=2014&modulus=2017

Iteration 4: Bit im Exponenten gesetzt 
faktor₄ = faktor₃² % m = 16² % 2017 = 256 
ergebnis₄ = ergebnis₃ * faktor₄ % m = 64 * 256 % 2017 = 248 

Iteration 5: Bit im Exponenten gesetzt
faktor₅ = faktor₄² % m = 256² % 2017 = 992
ergebnis₅ = ergebnis₄ * faktor₅ % m = 248 * 992 % 2017 = 1959

Iteration 6: Bit im Exponenten nicht gesetzt
faktor₆ = faktor₅² % m = 992² % 2017 = 1785
ergebnis₆ = ergebnis₅ = 1959 

---

leider nein :)

aber schön wär's!

die Schritte habe ich mir notiert, aber viel bringt mir das irgendwie nicht.

---

Müsstest du denn diese Rechnung noch begründen?
Viel Spass noch bei der weiterführenden Lektüre! Schönen Abend!