Restbestimmung (modulo-Rechnung)

13.08.2015, 15:30

Matheversteher

Restbestimmung (modulo-Rechnung)

Hallo alle zusammen, Wink

ich habe folgende Aufgabe:

ich soll den kleinsten nicht negativen Rest von $\begin{eqnarray*} 282148^{28661} \mod 105 \end{eqnarray*}$ bestimmen.

Ansatz:

Zuerst einmal reduziere ich 282148 modulo 105, der Rest ist 13
Dann weiß ich Dank Euler

$\begin{eqnarray*} 13^{48} \equiv 1 \mod 105 \end{eqnarray*}$
Somit habe ich noch
$\begin{eqnarray*} 13^9 \mod 105 \end{eqnarray*}$ , was
$\begin{eqnarray*} 8^8 \cdot 13 \mod 105 \end{eqnarray*}$ ergibt.
Reduzieren kann ich es bis $\begin{eqnarray*} 2^3 \cdot 23^3 \cdot 13 \mod 105 \end{eqnarray*}$

Allerding ist es immernoch ein weiter weg bis dass ich den Rest habe bzw. es ist auch mit einiger REchnerei verbunden.
Wie kann ich das ganze aber schnell lösen bzw. welche Regel kann ich anwenden?

Vielen Dank schinmal für eure Vorschläge smile

13.08.2015, 15:35

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Matheversteher
Dann weiß ich Dank Euler

$\begin{eqnarray*} 13^{48} \equiv 1 \mod 105 \end{eqnarray*}$
Somit habe ich noch
$\begin{eqnarray*} 13^9 \mod 105 \end{eqnarray*}$

Verstehe ich nicht: Es ist doch $\begin{align*} 28661\bmod 48 = 5 \end{align*}$ statt 9. verwirrt

Und die dann folgenden Zeilen werden immer verworrener - da blicke ich überhaupt nicht mehr durch, auf wessen Grundlage du da umformst. unglücklich

13.08.2015, 16:37

Brotscheibe

Auf diesen Beitrag antworten »

Sollst du das mit Zettel und Stift oder auch am PC ausrechnen? Auf Wiki oder auch anderen Seiten ist ein Algorithmus für modulare Exponentiation beschrieben der angenehm schnell ist. Zumindest am PC.

14.08.2015, 13:12

Matheversteher

Auf diesen Beitrag antworten »

Hallo ihr beiden Wink

Zitat:

Original von Brotscheibe
Sollst du das mit Zettel und Stift oder auch am PC ausrechnen? Auf Wiki oder auch anderen Seiten ist ein Algorithmus für modulare Exponentiation beschrieben der angenehm schnell ist. Zumindest am PC.

Ja das ganze soll via Fußweg berechnet werden. Ohne Taschenrechner etc.

Zitat:

Original von HAL 9000
Verstehe ich nicht: Es ist doch $\begin{eqnarray*} 28661 \mod 48=5 \end{eqnarray*}$ statt 9. Und die dann folgenden Zeilen werden immer verworrener - da blicke ich überhaupt nicht mehr durch, auf wessen Grundlage du da umformst.

In der Tat, da liegt der Fehler, der Rest mod 48 ist 5 Hammer

Ok, dann ist es natürlich
$\begin{eqnarray*} 13^5 = 13^2 \cdot 13^2 \cdot 13 = 169 \cdot 169 \cdot 13 \equiv 64 \cdot 64 \cdot 13 \mod 105 \end{eqnarray*}$

Die 64 habe ich der "Einfachheit" halber umgeformt in $\begin{eqnarray*} 64=2^6 \end{eqnarray*}$

--> $\begin{eqnarray*} 2^6 \cdot 2^6 \cdot 13 = 2^{12} \cdot 13 \mod 105 \end{eqnarray*}$

Ich hoffe ich habe jetzt nicht wieder irgendwo einen Fehler eingebaut. verwirrt

Aber das ist doch immer noch Rechnerei ohne Ende (gut hier übertreibe ich aber es ist immer noch langwierig für mod-Rechnungen).

____________________________________________

(In meinem Startpost habe ich es nach dem Umformen von 64 dann bei $\begin{eqnarray*} 8^8 \end{eqnarray*}$ belassen, wobei bei dem Exponenten der Fehler war).
Man muss natürlich sagen, das 28661 ein sehr großer Exponent ist und den mod 48 reduzieren auch recht lange dauert.

14.08.2015, 13:30

Brotscheibe

Auf diesen Beitrag antworten »

Bleibt am Ende 13...

Weil 2**12 = 4096; 4096 mod 105 = 1; 1 * 13 = 13. Ja oder ja?

14.08.2015, 13:35

HAL 9000

Auf diesen Beitrag antworten »

@Matheversteher

Mal ehrlich: Spätestens wenn du bei $\begin{align*} 13^5 \end{align*}$ angelangt bist, besteht m.E. kein Grund mehr für eine derartige Jammerei! Das bisschen $\begin{align*} 13^5\equiv 13\bmod 105 \end{align*}$ wird doch wohl hinzukriegen sein, auf welchem Wege auch immer. Augenzwinkern

Wenn dir das zuviel Rechnerei ist, kannst du ja alternativ die Ausgangszahl modulo 3, 5, 7 berechnen, und die erzielten Ergebnisse mittels chinesischem Restsatz wieder zusammenbasteln zu modulo 105. Ob das der bessere und schnellere Weg ist - Geschmackssache.

P.S.: Wenn du was kurzes für deinen Restweg suchst, dann vielleicht dies:

$\begin{align*} 13^4-1 = (13^2-1)(13^2+1) = 12\cdot 14\cdot 170 \end{align*}$ ist garantiert durch $\begin{align*} 3\cdot 7\cdot 5=105 \end{align*}$ teilbar, also ist $\begin{align*} 13^4\equiv 1\bmod 105 \end{align*}$ .

Neue Frage »

Antworten »

Restbestimmung (modulo-Rechnung)

Verwandte Themen