Restklasse berechnen

17.03.2020, 19:58	Versagt69	Auf diesen Beitrag antworten »
Restklasse berechnen Meine Frage: Hallo, aufgrund von Fernlehre kann ich kaum wen fragen und versuche es nun hier, meine Internetrecherche half nix darum greife ich zu drastischen Mittel und frage hier nach . 10779^5339 mod 21311 Wie berechnet man das, in einem online Rechner kommt 42 raus... Liebe Grüße Meine Ideen: Idee hätte ich keine....
17.03.2020, 20:03	Elvis	Auf diesen Beitrag antworten »
Nach Douglas Adams ist das Ergebnis völlig klar. Aber wie man dahin kommt, weiß ich auch nicht. Vielleicht 10 Millionen Jahre lang rechnen.
17.03.2020, 20:44	Leopold	Auf diesen Beitrag antworten »
Die folgenden Rechnungen werden in der Basis in $\begin{align} \mathbb{Z}_{21311} \end{align}$ durchgeführt. Durch fortwährendes Quadrieren kommt man ans Ziel. Zerlegung des Exponenten: $\begin{align} 5339 = 19 \cdot 281 \end{align}$ $\begin{align} 10779^2 = 20580 \end{align}$ $\begin{align} 10779^4 = 20580^2 = 1586 \end{align}$ $\begin{align} 10779^8 = 1586^2 = 698 \end{align}$ $\begin{align} 10779^{16} = 698^2 = 18362 \end{align}$ $\begin{align} 10779^{32} = 18362^2 = 1713 \end{align}$ $\begin{align} 10779^{64} = 1713^2 = 14762 \end{align}$ $\begin{align} 10779^{128} = 14752^2 = 11669 \end{align}$ $\begin{align} 10779^{256} = 11669^2 = 9582 \end{align}$ $\begin{align} 10779^{281} = 10779^{256} \cdot 10779^{16} \cdot 10779^8 \cdot 10779 = 9582 \cdot 18362 \cdot 698 \cdot 10779 \end{align}$ $\begin{align} = 1068 \cdot 698 \cdot 10779 = 20890 \cdot 10779 = 1284 \end{align}$ $\begin{align} 1284^2 = 7709 \end{align}$ $\begin{align} 1284^4 = 7709^2 = 13613 \end{align}$ $\begin{align} 1284^8 = 13613^2 = 14624 \end{align}$ $\begin{align} 1284^{16} = 14624^2 = 5491 \end{align}$ $\begin{align} 1284^{19} = 1284^{16} \cdot 1284^2 \cdot 1284 = 5491 \cdot 7709 \cdot 1284 \end{align}$ $\begin{align} = 6473 \cdot 1284 = 42 \end{align}$ $\begin{align} 10779^{5339} = \left( 10779^{281} \right)^{19} = 1284^{19} = 42 \end{align}$ Ganz zu Fuß (und mit dem Taschenrechner) - und schon sind 10 Millionen Jahre vorbei. Fachleute für Zahlentheorie können das sicher noch schneller. Irgendwelche koreanisch-indonesischen Restsätze oder so was. Mit Douglas Adams kann natürlich keiner mithalten.
17.03.2020, 20:48	tatmas	Auf diesen Beitrag antworten »
Hallo, ich würde als allererstes schauen ob der Modulus prim ist oder nicht, es ist Letzteres. In den Faktoren zu Rechnen ist deutlich angenehmer.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »