Modulo - Potenz

18.11.2011, 09:04

beli01

Modulo - Potenz

Meine Frage:
Morgen.

Ich versuche seit Tagen folgende Aufgabe zu lösen - leider trotz Internet ohne Erfolg :-(

$\begin{eqnarray*} 2^{100000} mod 100001 \end{eqnarray*}$

Es heißt, dass man nach folgender Umformung "ganz leicht auf 1024" kommt:
$\begin{eqnarray*} = (((((2^{2} * 2)^{2^{5}}*2)^{2}*2)^{4}*2)^{4}*2)^{2^{5}} \end{eqnarray*}$

Kann wer einen Tipp geben?

Meine Ideen:
- "nach jeder Multiplikation mod * rechnen
- Kunkruzenzregel $\begin{eqnarray*} a = b (mod m) -> a^{n} = b^{n} (mod m) \end{eqnarray*}$

Haben mir bisher keinen Erfolg beschert :-(

18.11.2011, 09:26

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von beli01
- Kunkruzenzregel

Wie bitte? ROFL

Zum eigentlichen Thema: Alternativ kommt man auch mit dem kleinen Fermat zum Ziel, unter Berücksichtigung der Primfaktorzerlegung $\begin{eqnarray*} 100001 = 11\cdot 9091 \end{eqnarray*}$ .

18.11.2011, 09:45

beli01

Auf diesen Beitrag antworten »

Diese Regel hatte ich im Netz gefunden (in einem Forum) Augenzwinkern

Hm ... hast du ein kleines Beispiel, wie man den kl. Fermat anwendet?
Habs mal versucht selbst zu verstehn (wiki) aber leider ohne Erfolg unglücklich

--

Das Problem ist ja, dass das alles händisch rechenbar sein soll.
Selbst wenn ich händisch schnell herausbekäme, dass

$\begin{eqnarray*} 2^{100000} mod 100001 = 2^{100000} mod 11 * 2^{100000} mod 9091 = 1 * 2^{100000} mod 9091 \end{eqnarray*}$

ist, kann man doch auf dem Papier $\begin{eqnarray*} 2^{100000} mod 9091 \end{eqnarray*}$ immer noch nicht "ganz einfach und schnell" ausrechnen, oder?

18.11.2011, 10:17

lgrizu

Auf diesen Beitrag antworten »

Was sagt denn der kleine Fermat aus?

$\begin{eqnarray*} a^{\phi(n)} \equiv 1 \mod n \end{eqnarray*}$ .

Nun bestimme einmal $\begin{eqnarray*} \phi(n) \end{eqnarray*}$ von n=10001 (Eulersche phi-Funktion).

Nutze dabei die Primfaktorzerlegung, die Rene dir bereits vorgegeben hat.

Und der Lacher: Es heißt Kongruenz. Augenzwinkern

18.11.2011, 13:53

beli01

Auf diesen Beitrag antworten »

Hm ... ich hatte das jetzt so interprediert:

1) $\begin{eqnarray*} 2^{p=100000} mod*(m=100001) \end{eqnarray*}$
2) $\begin{eqnarray*} => phi(m) = phi(11*9091) = 90900 = m_0 \end{eqnarray*}$
3) $\begin{eqnarray*} => 2^{p-m_0} \equiv 2^{9100} (mod*m) \end{eqnarray*}$

da $\begin{eqnarray*} 2^{9100} \end{eqnarray*}$ immernoch recht groß ist:

2) $\begin{eqnarray*} => phi(9100) = phi(2*2*5*5*7*13) = 4*6*12 = 1152 = m_1 \end{eqnarray*}$
3) $\begin{eqnarray*} => 2^{9100-x*m_1} \equiv 2^{1036} \end{eqnarray*}$

immer noch nicht klein genug ...

2) $\begin{eqnarray*} => phi(1036) = phi(2*2*7*37) = 6*36 = 216 = m_2 \end{eqnarray*}$
3) $\begin{eqnarray*} => 2^{1036-x*m_2} \equiv 2^{172} \end{eqnarray*}$

gefällt mir noch nicht ...

2) $\begin{eqnarray*} => phi(172) = phi(2*2*43) = 42 = m_3 \end{eqnarray*}$
3) $\begin{eqnarray*} => 2^{172-x*m_3} \equiv 2^{4} \equiv 16 (mod*m) \end{eqnarray*}$

!! Fehler -> es kommt nicht $\begin{eqnarray*} 1024 = 2^{10} \end{eqnarray*}$ raus :-(

----

Zitat:

Und der Lacher: Es heißt Kongruenz.

Komme aus Franken, dort gilt: g=k und d=t Wink

18.11.2011, 14:37

lgrizu

Auf diesen Beitrag antworten »

Warum du phi(9100) bestimmst ist mir nicht klar.

Du weißt folgendes:

$\begin{eqnarray*} 2^{100000} \equiv 2^{9100} \mod 100001 \end{eqnarray*}$

Und $\begin{eqnarray*} 2^{9090} \equiv 1 \mod 9091 \end{eqnarray*}$ und $\begin{eqnarray*} 2^{10} \equiv 1 \mod 11 \end{eqnarray*}$ .

Nun ist 90900+9090+10=100000, also eigentlich fertig.

18.11.2011, 15:15

beli01

Auf diesen Beitrag antworten »

Zitat:

$\begin{eqnarray*} 2^{9090} \equiv 1 \mod 9091 \end{eqnarray*}$ und
$\begin{eqnarray*} 2^{10} \equiv 1 \mod 11 \end{eqnarray*}$

Aber was bringt mir das Ergebnis von mod 11 / 9091 wenn ich doch mod des produktes habe?

$\begin{eqnarray*} 2^{9100} * (mod 100001) \equiv 2^{9090} 2^{10} * (mod 100001) \end{eqnarray*}$

meinetwegen vielleicht: (was ja falsch ist)

$\begin{eqnarray*} 2^{9090} 2^{10} * (mod 9091) * (mod 11) \equiv 1*1 \end{eqnarray*}$

-- tut mir wirklich Leid - aber du hilfst mir hier grad rieeeeßig smile

Danke schonmal!!

18.11.2011, 17:34

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von beli01
$\begin{eqnarray*} 2^{9090} 2^{10} * (mod 9091) * (mod 11) \equiv 1*1 \end{eqnarray*}$

Reste unterschiedlicher Module miteinander zu multiplizieren macht nicht den geringsten Sinn. unglücklich

Nein, es geht um die Lösung der gemeinsamen Kongruenz

$\begin{eqnarray*} x \equiv a \bmod m_1 \end{eqnarray*}$

$\begin{eqnarray*} x \equiv b \bmod m_2 \end{eqnarray*}$

für teilerfremde Module $\begin{eqnarray*} m_1,m_2 \end{eqnarray*}$ . Nach chinesischem Restsatz ist diese Lösung modulo $\begin{eqnarray*} m_1\cdot m_2 \end{eqnarray*}$ eindeutig. Im Fall $\begin{eqnarray*} a=b \end{eqnarray*}$ (wie hier a=b=1) ist diese Lösung auch sofort zu sehen: Es ist schlicht $\begin{eqnarray*} x\equiv a\bmod m_1 \cdot m_2 \end{eqnarray*}$

Im vorliegenden Fall ist $\begin{eqnarray*} 2^{9090} \equiv 1\bmod 9091 \end{eqnarray*}$ und auch $\begin{eqnarray*} 2^{9090} = \left( 2^{10} \right)^{909} \equiv 1\bmod 11 \end{eqnarray*}$ , und somit $\begin{eqnarray*} 2^{9090} \equiv 1\bmod 100001 \end{eqnarray*}$ .

Damit folgt letztlich $\begin{eqnarray*} 2^{100000} = 2^{9090\cdot 11 + 10} = \left( 2^{9090} \right)^{11} \cdot 2^{10} \equiv 2^{10} = 1024 \bmod 100001 \end{eqnarray*}$ .

-------------------------------------

Abschließend möchte ich dennoch eine Lanze für deinen ursprünglichen Weg über

$\begin{eqnarray*} 2^{100000} = (((((2^{2} * 2)^{2^{5}}*2)^{2}*2)^{4}*2)^{4}*2)^{2^{5}} \end{eqnarray*}$

brechen. Die nun anstehenden Modulo-Rechnungen sehen zwar viel umfangreicher aus als der obige Weg über Fermat, aber dabei vergisst man eine "Kleinigkeit": Die oben benutzte Primfaktorzerlegung (die ja auch nicht ohne Aufwand ermittelt wurde) ist bei diesem Weg nicht nötig. Augenzwinkern

18.11.2011, 18:27

beli01

Auf diesen Beitrag antworten »

Wow .... ich bin sprachlos Big Laugh

Besten Dank euch beiden für die ausführlichen Hilfestellungungen!
Ich glaube ich kann das nun endlich komplett nachvollziehen.

(Auch wenn die Bemerkung vom Prog "easy ausrechnen" nicht meiner Empfindung entspricht :P

Schönes Wochenende!

18.11.2011, 19:25

beli01

Auf diesen Beitrag antworten »

Kurze Frage noch:

Was mache ich falsch, wenn ich das gleiche bei $\begin{eqnarray*} 2^{100} \mod 100 \end{eqnarray*}$ versuche und:

$\begin{eqnarray*} 2^{100} => phi(100) = phi(5*5*2*2) = 4*4 = 16 \end{eqnarray*}$
Annahme wäre nun $\begin{eqnarray*} 2^{16} \equiv 1 \mod 100 \end{eqnarray*}$ , was jedoch nicht stimmt,
da $\begin{eqnarray*} 2^{16} \equiv 36 \mod 100 \end{eqnarray*}$ ist :-(

(Die Lösung der Rechnung weiß ich schon - 76 - habe ich mehr oder minder händisch erreichnet)

18.11.2011, 20:37

lgrizu

Auf diesen Beitrag antworten »

Wenn p eine Primzahl ist, dann ist $\begin{eqnarray*} \phi(p^n)=p^{n}-p^{n-1} \end{eqnarray*}$ , also $\begin{eqnarray*} \phi(5 \cdot 5)=5^2-5^1=20 \end{eqnarray*}$ , das selbe für phi(4).

Ist ja auch irgendwie klar, die phi-Funktion gibt ja die Anzahl der teilerfremden Zahlen an, und die Zahlen, die nicht teilerfremd zu 25 sind sind 5,10,15,20,25.

18.11.2011, 20:40

beli01

Auf diesen Beitrag antworten »

Zitat:

Original von lgrizu
Wenn p eine Primzahl ist....

Danke !! Das wars smile

19.11.2011, 10:39

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von beli01
Was mache ich falsch, wenn ich das gleiche bei $\begin{eqnarray*} 2^{100} \mod 100 \end{eqnarray*}$ versuche und:

$\begin{eqnarray*} 2^{100} => phi(100) = phi(5*5*2*2) = 4*4 = 16 \end{eqnarray*}$
Annahme wäre nun $\begin{eqnarray*} 2^{16} \equiv 1 \mod 100 \end{eqnarray*}$ , was jedoch nicht stimmt,
da $\begin{eqnarray*} 2^{16} \equiv 36 \mod 100 \end{eqnarray*}$ ist

Abgesehen von der falschen Phi-Berechnung (auf die lgrizu schon hingewiesen hat) hast du außerdem die wichtigste Voraussetzung des Satzes von Fermat-Euler

$\begin{eqnarray*} a^{\varphi(m)} \equiv 1 \bmod m \end{eqnarray*}$

nicht beachtet: $\begin{eqnarray*} a \end{eqnarray*}$ und $\begin{eqnarray*} m \end{eqnarray*}$ müssen teilerfremd sein!

Bei $\begin{eqnarray*} a=2 \end{eqnarray*}$ und $\begin{eqnarray*} m=100 \end{eqnarray*}$ ist das offenkundig nicht der Fall. unglücklich

-----------------------------------------------------

Eine Anmerkung zum Schluss: Noch passender als die Eulersche Phi-Funktion ist die Carmichael-Funktion für solche Potenzuntersuchungen. Im vorliegenden Fall ist

$\begin{eqnarray*} \lambda(100001) = \lambda(11\cdot 9091) = \operatorname{kgV}(10,9090) = 9090 \end{eqnarray*}$ ,

d.h. es ist bereits $\begin{eqnarray*} a^{9090} \equiv 1\bmod 100001 \end{eqnarray*}$ für jede zu 100001 teilerfremde Zahl $\begin{eqnarray*} a \end{eqnarray*}$ . Genau das habe ich oben benutzt.

19.11.2011, 12:56

lgrizu

Auf diesen Beitrag antworten »

Man kann hier auch benutzen (eigentzlih kennt man die Zweierpotenzen ja ein wenig, Rechnerzeitalter Augenzwinkern

), dass $\begin{eqnarray*} 2^{10} \equiv 24 \mod 100 \end{eqnarray*}$ ist, also $\begin{eqnarray*} 2^{20} \equiv 76 \mod 100 \end{eqnarray*}$ . Nun sind die letzten beiden Stellen einer Potenz von 76 immer die 76, wie sich einfach veranschaulichen lässt, es ist 6*6=36, die letzte Stelle ist also eine 6.
Nun ist 6*70=420, addieren wir zu der 20 die 30 von der 36 dazu erhalten wir 50. Nun kommt die 20 noch einmal dazu, weil wir nun 70*6=420 noch mal rechnen müssen, also 50+20=70.

Man kann sich das mit der Multiplikation, wie man sie in der Grundschule lernt auch veranschaulichen:

......76*......76
-------------------
......56
......20
-----------------
.......76

Neue Frage »

Antworten »

Modulo - Potenz

Verwandte Themen