Welcher Rest entsteht bei der Division durch 101 von 17^9932

Question

Ich weiß, dass ich hier mit Fermat arbeiten muss. Aber der Rest, der dann übrig bleibt, ist immer noch ziemlich hoch. Wie geht es dann weiter?

Answer 1

Mathemagiker,

Deine Vermutung, dass man den Ausdruck mit dem kleinen Satz von Fermat vereinfachen kann, stimmt. Es ist 101 eine Primzahl und deshalb gilt: $$\varphi(101) = 101-1 =100$$ Der Exponent 9932 setzt sich wie folgt zusammen: $$9932 = 99 \cdot \underbrace{100}_{\varphi(101) }$$ und demzufolge gilt: $$17^{99\cdot 100 + 32}=\underbrace{17^{99\cdot 100}}_{\equiv 1\mod 101}\cdot 17^{32}= 17^{32}$$ Nun kannst Du "schnelle Exponentiation" verwenden, um den verbleibenden Exponenten modulo 100 zu berechnen. Dafür wandeln wir 32 zunächst in eine Binärzahl um und rechnen dann folgendermaßen: 

Zusammenfassend gilt folglich: $$17^{9932} \equiv 87 \mod 101$$

Hilft Dir das weiter?

Viel Grüße

André, savest8

Comments

Hey save Okay, das muss ich mir wohl noch mal anschaun. Danke:-)

---

Danke für die "Beste Antwort";-) Kleiner Nachtrag: Es gilt natürlich $$32_{(10)}=100000_{(2)}$$ (Syntax).

---

Kontrolle mit

http://www.lamprechts.de/gerd/php/RechnerMitUmkehrfunktion.php

PowPowMod(17,9932,1,101)=87

stimmt.

Und um universell auf 32 zu kommen gibt es die Funktion

9932 mod CarmichaelLambda(101) = 32

---

Was ist denn CarmichaelLambda? Habe ich noch nie gehört.

---

Wenn Du auf den LINK von mir geklickt hättest, würdest Du unter der PowPowMod-

Funktion das Bild mit dem Abkürzungs-Gesetz sehen...

könntest per "suche Funktion" nach CarmichaelLambda suchen und würdest auf

OEIS-Folge A02322 hingewiesen: f(y)=OEIS(2322,y) oder mehr unter

http://oeis.org/A002322

oder http://mathworld.wolfram.com/CarmichaelFunction.html

oder https://de.wikipedia.org/wiki/Carmichael-Funktion

Answer 2

Nach dem kleinen Satz von Fermat gilt 17¹⁰⁰≡1 mod 101. Dann kann es Teiler t von 100 geben, für die           17^t≡1 mod 101. Ein solcher Teiler ist z.B. 10.  Es gilt 17¹⁰≡1 mod 101. 17⁹⁹³² = 17⁹⁹³⁰⁺². Jetzt muss nur noch 17²≡87 mod 101 berechnet werden, dann ist auch  17⁹⁹³²≡87 mod 101.