Modulo / Satz von Fermat

25.10.2008, 11:06	Gebhard	Auf diesen Beitrag antworten »
Modulo / Satz von Fermat Hallo, Ich habe folgendes Problem: *Berechnen Sie möglichst effitient* *a) 2^167 mod 83* *b) 3^167 mod 17* *Beide Aufgaben sollen in kurzer Zeit von Hand lösbar sein, wenn man den kleinen Satz von Fermat benutzt und berücksichtigt, dass 83 ind 17 Primzahlen sind.* Soweit zur Aufgabe. ich weiß, dass der satz von Fermat besagt, dass x^(p-1) = 1 mod p ich seh aber nicht ganz, wie mir das hier weiter helfen soll.... Wäre echt super, wenn mir jemand auf die Sprünge helfen könnte! Grüße, Gebhard
25.10.2008, 11:22	kiste	Auf diesen Beitrag antworten »
Hallo, du weißt doch bereits dass $\begin{eqnarray} 2^{82} \equiv 1 \mod 83 \end{eqnarray}$ und $\begin{eqnarray} 3^{16} \equiv 1 \mod 17 \end{eqnarray}$ . Wende das mehrmals an
25.10.2008, 11:55	Gebhard	Auf diesen Beitrag antworten »
Kannst du mir ein Beispiel geben, wie du das meinst? Ich steh heut echt mit beiden Füßen aufm Schlauch.
25.10.2008, 12:01	kiste	Auf diesen Beitrag antworten »
Es ist $\begin{eqnarray} 2^{167} = 2^3\cdot 2^{82} \cdot 2^{82} \end{eqnarray}$ . Mehr kann man echt nicht mehr sagen
25.10.2008, 12:24	Gebhard	Auf diesen Beitrag antworten »
OMG, es fällt mir wie Schuppen von den Augen! Danke!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »