Trick beim Modulorechnen

06.01.2012, 17:07	Kerze	Auf diesen Beitrag antworten »
Trick beim Modulorechnen Die Aufgabe lautet 3^16 (mod 22). Ich hatte solche Aufgaben schon in einem anderen Semester und bin der Meinung, dass es da einen Trick gab, um eine solche Aufgabe im Kopf zu rechnen...kann mir jemand auf die Sprünge helfen?!
06.01.2012, 17:27	HAL 9000	Auf diesen Beitrag antworten »
Eine elegante Variante wäre $\begin{eqnarray} 3^{16} \equiv 3\cdot (3+22)^{15} = 3\cdot 5^{30} \bmod 22 \end{eqnarray}$ und dann liefert Fermat-Euler mit $\begin{eqnarray} \varphi(22)=10 \end{eqnarray}$ schnell das Ergebnis. Es geht aber auch konventionell über $\begin{eqnarray} 3^{16} = \left( \left( \left( 3^2 \right)^2 \right)^2 \right)^2 \end{eqnarray}$ recht schnell.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »