Satz Euler-Fermat

14.12.2018, 16:12

Adramelec

Satz Euler-Fermat

Hallo,
folgende Aufgabe:
Für jede natürlich Zahl $\begin{eqnarray*} m \end{eqnarray*}$ gilt: $\begin{eqnarray*} m^{13} mod \thinspace 10 = m \thinspace mod \thinspace10 \end{eqnarray*}$
(Lösungsansatz über den Satz von Euler-Fermat)

Der Satz von Euler-Fermat ist ja:
$\begin{eqnarray*} a^{\phi{(n)}} \equiv 1 (mod \thinspace n) \end{eqnarray*}$

Ich weiß nicht, wie ich davon ableiten soll, dass die obere Aussage stimmt. Hat hier vielleicht jemand ein "Schubs" für mich in die richtige Richtung?

Danke! smile

14.12.2018, 16:32

HAL 9000

Auf diesen Beitrag antworten »

Passender ist eigentlich der pure Fermat in der Form $\begin{eqnarray*} a^p\equiv a\bmod p \end{eqnarray*}$ für Primzahlen $\begin{eqnarray*} p \end{eqnarray*}$ , denn der gilt nicht nur für die zu $\begin{eqnarray*} p \end{eqnarray*}$ teilerfremden $\begin{eqnarray*} a \end{eqnarray*}$ , sondern für alle $\begin{eqnarray*} a \end{eqnarray*}$ .

Du kannst natürlich auch Fermat-Euler verwenden, musst dann aber die nicht zu 10 teilerfremden Werte $\begin{eqnarray*} a \end{eqnarray*}$ bzw. $\begin{eqnarray*} m \end{eqnarray*}$ extra diskutieren.

14.12.2018, 22:06

Adramelec

Auf diesen Beitrag antworten »

Hmm, ok. Aber der "pure" Fermat passt ja in dem Fall nicht ganz.
Weil das p als Exponent von a dargestellt, ja nicht der gleiche Wert ist wie bei mod p in meiner Angabe.

Vorallem das p als Exponent von a muss ja teilerfremd zu a sein, aber wenn a= 26 ist und p 13 mod 10, kommt trotzdem 6 als Ergebnis raus.

Also ganz durchblickt habe ich es noch nicht :/

14.12.2018, 22:49

HAL 9000

Auf diesen Beitrag antworten »

Man kann das Modul ja gemäß seiner darin enthaltenen Primfaktoren bzw. Primfaktorpotenzen aufschlüsseln: In dem Sinne ist $\begin{eqnarray*} m^{13}\equiv m\bmod 10 \end{eqnarray*}$ äquivalent zum gleichzeitigen Bestehen der Kongruenzen $\begin{eqnarray*} m^{13}\equiv m\bmod 2 \end{eqnarray*}$ und $\begin{eqnarray*} m^{13}\equiv m\bmod 5 \end{eqnarray*}$ , und so habe ich meinen Tipp auch gemeint.

Tatsächlich liefert Fermat ja nicht nur $\begin{eqnarray*} m^p\equiv m\bmod p \end{eqnarray*}$ , sondern iterativ sogar $\begin{eqnarray*} m^{k(p-1)+1}\equiv m\bmod p \end{eqnarray*}$ für alle ganzen Zahlen $\begin{eqnarray*} k\geq 0 \end{eqnarray*}$ .

Wählt man in dieser Weise $\begin{eqnarray*} k=12 \end{eqnarray*}$ für $\begin{eqnarray*} p=2 \end{eqnarray*}$ , so ist man bei $\begin{eqnarray*} m^{13} = m^{12\cdot (2-1)+1} \equiv m\bmod 2 \end{eqnarray*}$ . Genauso führt $\begin{eqnarray*} k=3 \end{eqnarray*}$ für $\begin{eqnarray*} p=5 \end{eqnarray*}$ zu $\begin{eqnarray*} m^{13} = m^{3\cdot (5-1)+1} \equiv m\bmod 5 \end{eqnarray*}$ .

15.12.2018, 14:21

Adramelec

Auf diesen Beitrag antworten »

Okay, woher kommt die Herleitung zu $\begin{eqnarray*} m^{k(p-1)+1} \equiv \thinspace m \thinspace mod \thinspace p \end{eqnarray*}$ ?

Zumindestens für mich ist das nicht offensichtlich smile

Noch eine Frage, zu deinem Satz oben.. wenn ich das richtig verstanden habe, sagst du da folgendes:
$\begin{eqnarray*} m^{13} \equiv m \thinspace mod \thinspace 10 \end{eqnarray*}$ ist gleichwertig mit:
$\begin{eqnarray*} m^{13} \equiv m \thinspace mod \thinspace 2 \wedge m^{13} \equiv m \thinspace mod \thinspace 5 \end{eqnarray*}$

Also, wenn man das Ergebnis (also von mod 5 und mod 2) zusammenrechnet, muss das gleiche rauskommen als wie würde ich gleich mod 10 nehmen, korrekt? Was ja offensichtlich nicht stimmen kann? Also habe ich da irgendwas falsch verstanden.

Sorry für die Fragen, vermutlich ist das alles total offensichtlich und einfach - aber für mich grad eben nicht. Hammer

15.12.2018, 18:08

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Adramelec
Okay, woher kommt die Herleitung zu $\begin{eqnarray*} m^{k(p-1)+1} \equiv \thinspace m \thinspace mod \thinspace p \end{eqnarray*}$ ?

Per vollständiger Induktion. Start $\begin{eqnarray*} k=0 \end{eqnarray*}$ ist offensichtlich, der Induktionsschritt $\begin{eqnarray*} k\to (k+1) \end{eqnarray*}$ klappt so

$\begin{eqnarray*} m^{(k+1)(p-1)+1} = m^{k(p-1)+p} = m^{k(p-1)}\cdot m^p \stackrel{(F)}{=} m^{k(p-1)}\cdot m = m^{k(p-1)+1} \stackrel{(IV)}{=} m\bmod p \end{eqnarray*}$ .

Zitat:

Original von Adramelec
Also, wenn man das Ergebnis (also von mod 5 und mod 2) zusammenrechnet, muss das gleiche rauskommen als wie würde ich gleich mod 10 nehmen, korrekt?

Wenn du unter zusammenrechnen das verstehst, was ich oben geschrieben habe: Ja.

Zitat:

Original von Adramelec
Was ja offensichtlich nicht stimmen kann?

Was bitte stimmt "offensichtlich" nicht??? Erstaunt1

15.12.2018, 19:55

Adramelec

Auf diesen Beitrag antworten »

Wenn m=8 ist.
$\begin{eqnarray*} 8^{13} mod \thinspace 5 = 3 \end{eqnarray*}$
und
$\begin{eqnarray*} 8^{13} mod \thinspace 2 = 0 \end{eqnarray*}$

3+0 = 3 und nicht 8. Daher stimmt es "offensichtlich" nicht für mich.

Danke für die Erklärung mittels vollständiger Induktion :-)

15.12.2018, 21:31

HAL 9000

Auf diesen Beitrag antworten »

Wer spricht denn hier von Addition der Modulo-Berechnungen? Ich jedenfalls nicht, das hast du dir zusammenphantasiert. Forum Kloppe

Anscheinend verwechselst du das Ergebnis der zweistelligen Modulo-Operation $\begin{eqnarray*} a\bmod m=b \end{eqnarray*}$ mit der Kongruenzgleichung $\begin{eqnarray*} a\equiv b\bmod m \end{eqnarray*}$ :

Aus ersterem folgt letzteres, aber nicht umgekehrt!

Es geht bei den Betrachtungen hier nicht um $\begin{eqnarray*} 8^{13}\bmod 5 = 3 \end{eqnarray*}$ , sondern um $\begin{eqnarray*} 8^{13}\equiv 8\bmod 5 \end{eqnarray*}$ , genauso wenig ist hier $\begin{eqnarray*} 8^{13}\bmod 2 = 0 \end{eqnarray*}$ von Interesse, sondern $\begin{eqnarray*} 8^{13}\equiv 8\bmod 2 \end{eqnarray*}$ .

Und aus $\begin{eqnarray*} 8^{13}\equiv 8\bmod 5 \end{eqnarray*}$ und $\begin{eqnarray*} 8^{13}\equiv 8\bmod 2 \end{eqnarray*}$ folgt $\begin{eqnarray*} 8^{13}\equiv 8\bmod 10 \end{eqnarray*}$ , nichts weiter habe ich oben gesagt.

Neue Frage »

Antworten »

Satz Euler-Fermat

Verwandte Themen