Der kleine Satz von Fermat...

Benutzeravatar
oren78
BSc Spammer
BSc Spammer
Beiträge: 1373
Registriert: 17. Nov 2006 17:47
Wohnort: Darmstadt

Der kleine Satz von Fermat...

Beitrag von oren78 »

hallo miteinander,

wollte mich mal kurz informieren ob ich den satz richtig verstanden habe, wenn ich folgendes gegeben hab...

\(3^{1796}\;mod\;23\)

dann gilt laut Fermat's Theorem...

\(gcd(a,\; m)\; =\; 1\;\Rightarrow\;\;a^{\phi(m)}\;\equiv\;1\;mod\;m\)

und somit also...

\(3^{1796}\;\equiv\;3^{22}\;\equiv\;1\;mod\;23\)

gibt es da noch irgendwelche zwischenschritte zu beachten (z.B die schnelle Exponention mit der 3^22) mod 23
oder kann man das direkt so ohne weiteres niederschreiben...? hab halt keine lust wegen sowas punkte einzubüßen ;-)
"Unter allen menschlichen Entdeckungen sollte die Entdeckung der Fehler die wichtigste sein.", Stanisław Jerzy Lec

Christoph-D
Computerversteher
Computerversteher
Beiträge: 325
Registriert: 11. Dez 2005 13:14
Wohnort: Darmstadt

Re: Der kleine Satz von Fermat...

Beitrag von Christoph-D »

oren78 hat geschrieben:wollte mich mal kurz informieren ob ich den satz richtig verstanden habe, wenn ich folgendes gegeben hab...

\(3^{1796}\;mod\;23\)

dann gilt laut Fermat's Theorem...

\(gcd(a,\; m)\; =\; 1\;\Rightarrow\;\;a^{\phi(m)}\;\equiv\;1\;mod\;m\)
Stimmt soweit.
oren78 hat geschrieben: und somit also...

\(3^{1796}\;\equiv\;3^{22}\;\equiv\;1\;mod\;23\)
Wie kommst du von \(3^{1796}\) auf \(3^{22}\)?
Du hast doch oben vorgerechnet, dass \(a^{\phi(m)} \equiv 1 \mod m\) ist, also hier konkret: \(3^{22} \equiv 1 \mod 23\).

Dann ist \(3^{1796} \equiv 3^{22 \cdot 81 + 14} \equiv \left(3^{22}\right)^{81} \cdot 3^{14} \equiv 1^{81} \cdot 3^{14} \equiv 3^{14} \mod 23\).
"I believe in the fundamental interconnectedness of all things." (Dirk Gently)

Benutzeravatar
oren78
BSc Spammer
BSc Spammer
Beiträge: 1373
Registriert: 17. Nov 2006 17:47
Wohnort: Darmstadt

Re: Der kleine Satz von Fermat...

Beitrag von oren78 »

Christoph-D hat geschrieben:
\(3^{1796}\;\equiv\;3^{22}\;\equiv\;1\;mod\;23\)
hab doch gewusst das da noch was fehlt ;-)
Christoph-D hat geschrieben: Du hast doch oben vorgerechnet, dass \(a^{\phi(m)} \equiv 1 \mod m\) ist, also hier konkret: \(3^{22} \equiv 1 \mod 23\).

Dann ist \(3^{1796} \equiv 3^{22 \cdot 81 + 14} \equiv \left(3^{22}\right)^{81} \cdot 3^{14} \equiv 1^{81} \cdot 3^{14} \equiv 3^{14} \mod 23\).
wie überträgst du die potenz von 81 auf die basis 1? das leuchtet mir nicht ganz ein...sind doch verschiedene basen
und woher kommt jetzt das +14 in der potenz von der 3 genau her?
"Unter allen menschlichen Entdeckungen sollte die Entdeckung der Fehler die wichtigste sein.", Stanisław Jerzy Lec

Benutzeravatar
Tristan
Windoof-User
Windoof-User
Beiträge: 29
Registriert: 22. Okt 2008 20:32

Re: Der kleine Satz von Fermat...

Beitrag von Tristan »

wie überträgst du die potenz von 81 auf die basis 1?
Das kann er machen, weil (wie oben schon geschrieben) \(3^{22}\equiv 1\mod 23\) gilt. Und die 14 kommt daher, dass eben \(1796=22\cdot81+14\) gilt. Rechne es nach!

Christoph-D
Computerversteher
Computerversteher
Beiträge: 325
Registriert: 11. Dez 2005 13:14
Wohnort: Darmstadt

Re: Der kleine Satz von Fermat...

Beitrag von Christoph-D »

oren78 hat geschrieben:
Christoph-D hat geschrieben:
\(3^{1796}\;\equiv\;3^{22}\;\equiv\;1\;mod\;23\)
hab doch gewusst das da noch was fehlt ;-)
Christoph-D hat geschrieben: Du hast doch oben vorgerechnet, dass \(a^{\phi(m)} \equiv 1 \mod m\) ist, also hier konkret: \(3^{22} \equiv 1 \mod 23\).

Dann ist \(3^{1796} \equiv 3^{22 \cdot 81 + 14} \equiv \left(3^{22}\right)^{81} \cdot 3^{14} \equiv 1^{81} \cdot 3^{14} \equiv 3^{14} \mod 23\).
wie überträgst du die potenz von 81 auf die basis 1? das leuchtet mir nicht ganz ein...sind doch verschiedene basen
und woher kommt jetzt das +14 in der potenz von der 3 genau her?
Das +14 kommt daher, dass \(1796 = 22 \cdot 81 + 14\) ist.

Der Schritt \(\left(3^{22}\right)^{81} \cdot 3^{14} \equiv 1^{81} \cdot 3^{14} \mod 23\) nimmt nur die Gleichung \(3^{22} \equiv 1 \mod 23\) zu Hilfe.
"I believe in the fundamental interconnectedness of all things." (Dirk Gently)

Benutzeravatar
oren78
BSc Spammer
BSc Spammer
Beiträge: 1373
Registriert: 17. Nov 2006 17:47
Wohnort: Darmstadt

Re: Der kleine Satz von Fermat...

Beitrag von oren78 »

oh man :oops: steh heute aber gewaltig auf der leitung...alles klar vielen dank euch beiden ;-)
"Unter allen menschlichen Entdeckungen sollte die Entdeckung der Fehler die wichtigste sein.", Stanisław Jerzy Lec

Antworten

Zurück zu „Archiv“