satz von fermat und rest

05.12.2012, 15:25	marlex1	Auf diesen Beitrag antworten »
satz von fermat und rest Meine Frage: wie kriege ich den rest von 3^1000 beim teilen durch 19, irgendwie soll mir dabei der satz von fermat helfen, der ja besagt: n^p-1 ? 1 (mod p) p ist eine primzahl, n ist eine natürliche zahl nun sind aber 3 und 19 primzahlen und mir ist auch nicht klar, was n sein soll (1000, 3 oder 19). ich verstehe leider auch nicht, was mir hier sagen soll Meine Ideen: ich nehme mal an 19 ist die primzahl, da ich durch 19 teile und n wird dann wohl die 3 sein, hab ich einfach mal so beschlossen, da beide einen exponenten haben was mache ist jetzt? ich habe all diese schlüsse aus größter unsicherheit gezogen, in einer klausur wüsste ich also nicht gerade was zu tun wäre, es wäre also ausgesprochen hilfreich, wenn mir einer den sinn hinter dieser vorgehensweise erklären könnte...
05.12.2012, 19:03	weisbrot	Auf diesen Beitrag antworten »
RE: satz von fermat und rest ja, der ansatz hört sich schonmal gut an. dann solltest du zum lösen ein paar rechenregeln fürs teilen bzw. rechnen mit mod(etwas) kennen und anwenden, z.b. $\begin{eqnarray} a^b \mod n = (a \mod n)^b \mod n \end{eqnarray}$ und/oder $\begin{eqnarray} (a\cdot b)\mod n = ((a \mod n)\cdot (b \mod n)) \mod n \end{eqnarray}$ . dann kannst du versuchen deinen ausdruck so zu vereinfachen dass du das leicht ausrechnen kannst. lg
05.12.2012, 20:09	HAL 9000	Auf diesen Beitrag antworten »
Der kleine Fermat hilft bei der "Reduzierung des Exponenten", im Klartext: Wenn du $\begin{eqnarray} n^m\bmod p \end{eqnarray}$ für "große" Exponenten $\begin{eqnarray} m \end{eqnarray}$ berechnen sollst, dann dividierst du zuerst mal $\begin{eqnarray} m \end{eqnarray}$ durch $\begin{eqnarray} (p-1) \end{eqnarray}$ mit Rest, d.h. du ermittelst Quotient $\begin{eqnarray} q \end{eqnarray}$ und Rest $\begin{eqnarray} r \end{eqnarray}$ mit $\begin{eqnarray} m = q(p-1)+r \end{eqnarray}$ wobei $\begin{eqnarray} 0\leq r<p-1 \end{eqnarray}$ . Denn nach Potenzgesetzen sowie dem Kleinen Fermat ist ja dann $\begin{eqnarray} n^m = n^{q(p-1)+r} \stackrel{PG}{=} \left( n^{p-1} \right)^q \cdot n^r \stackrel{KF}{=} 1^{q} \cdot n^r = n^r \bmod p \end{eqnarray}$ , d.h., Exponent $\begin{eqnarray} m \end{eqnarray}$ ist in der Berechnung auf den i.d.R. sehr viel kleineren Exponenten $\begin{eqnarray} r \end{eqnarray}$ "eingedampft" worden. Gilt selbstredend nur für $\begin{eqnarray} n \end{eqnarray}$ , die nicht durch $\begin{eqnarray} p \end{eqnarray}$ teilbar sind. P.S.: Wenn man rechenfaul ist (wie ich), würde man auch noch andere Kniffe hinzuziehen, wie z.B. $\begin{eqnarray} 3^{1000} \equiv (-16)^{1000} = 4^{2000} \bmod 19 \end{eqnarray}$ Aber das ist nicht unbedingt nötig, man kommt auch so (mit vielleicht etwas aufwändigerer Rechnung) ans Ziel.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »