Modulares Rechnen Multiplikation

11.05.2007, 19:08	Celtic_Princess	Auf diesen Beitrag antworten »
Modulares Rechnen Multiplikation Die Aufgabe ist folgende: Wie lauten die letzten beiden Ziffern der Zahl 777^999? Rechenvorgang: 77294121418161*21 mod 100 im Skript steht dann folgendes Ergebnis: 13 mod 100 Ist das ein Fehler im Skript? Bei mir kommt da überhautp nichts raus, was mit 13 zu tun hätte!
11.05.2007, 19:59	AD	Auf diesen Beitrag antworten »
13 ist richtig: Da 777 und 100 teilerfremd sind, kann man das auch so sehen: Aus $\begin{eqnarray} 777^{40} = 777^{\varphi(100)} \equiv 1\mod 100 \end{eqnarray}$ folgt auch $\begin{eqnarray} 777^{1000} = (777^{40})^{25} \equiv 1\mod 100 \end{eqnarray}$ , und wegen $\begin{eqnarray} 13\cdot 77=1001 \end{eqnarray}$ daraus dann $\begin{eqnarray} 13 \equiv 13\cdot 777^{1000} \equiv (13\cdot 77)\cdot 777^{999} \equiv 777^{999}\mod 100 \end{eqnarray}$
14.05.2007, 07:35	Celtic_Princess	Auf diesen Beitrag antworten »
- Das sieht kompliziert aus, aber ich hoff, ich versteh das die nächsten Tage noch. Ansonsten meld ich mich nochmal !
14.05.2007, 12:45	AD	Auf diesen Beitrag antworten »
Re: - Es soll auch nur eine alternative Berechnungsweise sein. Du hast die Potenz vermutlich so berechnet, dass du die Binärzerlegung $\begin{eqnarray} 999 = [1111100111]_2 \end{eqnarray}$ des Exponenten 999 herangezogen hast und dann diejenigen iterierten Potenzen $\begin{eqnarray} 77^{2^m} \end{eqnarray}$ herangezogen hast, die eine 1 in dieser Binärdarstellung haben, so wie hier: Modulo-Rechnung Das ist auf jeden Fall die Methode, die immer und robust klappt.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »