Der kleine Satz von Fermat...

[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

[Christoph-D]

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.

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\).

[oren78]

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

hab doch gewusst das da noch was fehlt

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?

[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]

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

hab doch gewusst das da noch was fehlt

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.

[oren78]

oh man steh heute aber gewaltig auf der leitung...alles klar vielen dank euch beiden