Satz von Euler-Fermat

16.01.2021, 18:37

Riesenfaultier

Satz von Euler-Fermat

Hallo,

Leider habe ich wieder mal ein Problem bei einem Übungsbeispiel und ich hoffe ihr könnt mir dabei helfen.

Folgende Angabe:
Zeigen Sie:
Für jede Natürliche Zahl m gilt: $\begin{eqnarray*} m^{13} mod 10 = m \ mod 10 \end{eqnarray*}$
(Tipp: Lösungsansatz über den Satz von Euler Fermat)

Bei der Anwendung des Euler Fermats habe ich mal das Phi von m berechnet.
$\begin{eqnarray*} \varphi(m) = \varphi(10) = 10 * \frac{1}{2} *\frac{4}{5} = 4 \end{eqnarray*}$

Somit kamen wir zur Folgerung:

$\begin{eqnarray*} m^{4}*m^{4}*m^{4}*m^{1} = m \mod 10 \end{eqnarray*}$

Leider kommen wir hier nicht weiter, da wir keinen Ansatz haben wie wir von diesem Schritt auf den Beweis kommen.

lg.

16.01.2021, 18:45

Leopold

Auf diesen Beitrag antworten »

Aber es ist doch gerade

$\begin{align*} m^{\varphi(10)} \equiv 1 \bmod{10} \end{align*}$

16.01.2021, 18:50

Riesenfaultier

Auf diesen Beitrag antworten »

Hi,

Entschuldige bitte ich habe aus versehen in der Angabe Kongurent statt = geschrieben.

lg.

16.01.2021, 18:59

Leopold

Auf diesen Beitrag antworten »

Aber "gleich" ergibt doch für Kongruenzen keinen Sinn. Es sei denn, du arbeitest statt in $\begin{align*} \mathbb{Z} \end{align*}$ im Ring $\begin{align*} \mathbb{Z}_{10} \end{align*}$ der Restklassen modulo 10 und identifizierst alle ganzen Zahlen, die sich nur um 10 unterscheiden. Dann wird aus der Kongruenz Gleichheit. Dann ergibt allerdings "modulo" wiederum keinen Sinn.

16.01.2021, 19:14

Riesenfaultier

Auf diesen Beitrag antworten »

Hi,

Leider kann ich zur Sinnhaftigkeit der Angabe keine Auskunft treffen, jedoch konnte ich gerade eine Lösung im Forum finden welche ich leider auch nicht zur Gänze verstehe.

Thread:
threadid=589324
(Ich darf leider keine URLs posten)

Bei dem beschriebenen Beispiel wird der "pure" Fermat angewendet.

Leider verstehe ich nicht wie er vom Beispiel der form m^a mod n = m mod n auf die Form

$\begin{eqnarray*} m^n \equiv m\mod n \end{eqnarray*}$ kommt.

16.01.2021, 19:25

Leopold

Auf diesen Beitrag antworten »

Ehrlich gesagt, verstehe ich dein Problem nicht. Du hast die Aufgabe doch längst gelöst.

$\begin{align*} \varphi(10)=4 \end{align*}$

Daher:

$\begin{align*} m^4 \equiv 1 \bmod{10} \end{align*}$

Die Kongruenz in die dritte Potenz erheben:

$\begin{align*} m^{12} \equiv 1 \bmod{10} \end{align*}$

Die Kongruenz mit $\begin{align*} m \end{align*}$ multiplizieren:

$\begin{align*} m^{13} \equiv m \bmod{10} \end{align*}$

Beim Addieren, Subtrahieren und Multiplizieren kann man ja mit Kongruenzen wie mit Gleichungen rechnen. Schwierig wird es nur beim Dividieren oder Kürzen.

Beispiele:

$\begin{align*} \color{red} 4 \color{black} ^{13} = 6710886 \color{red} 4 \end{align*}$

$\begin{align*} \color{red} 7 \color{black} ^{13} = 9688901040 \color{red} 7 \end{align*}$

$\begin{align*} \color{red} 9 \color{black} ^{13} = 254186582832 \color{red} 9 \end{align*}$

16.01.2021, 19:44

Riesenfaultier

Auf diesen Beitrag antworten »

Hi,

Vielen Dank für diesen kurzen Wachrüttler. Forum Kloppe

Wir sahen anscheinend den Wald vor lauter Bäumen nicht mehr.

lg.

16.01.2021, 20:39

HAL 9000

Auf diesen Beitrag antworten »

Wenn ich so denn Thread durchgehe, dann wurde bisher nur $\begin{eqnarray*} m^{13}\equiv m\bmod 10 \end{eqnarray*}$ für die $\begin{eqnarray*} m \end{eqnarray*}$ bewiesen, die teilerfremd (!) zu 10 sind, denn nur für die gilt die benutzte Aussage $\begin{eqnarray*} m^{\varphi(10)} = m^4\equiv 1\bmod 10 \end{eqnarray*}$ . geschockt

Gefordert war jedoch der Nachweis für alle natürlichen Zahlen $\begin{eqnarray*} m \end{eqnarray*}$ .

Ich würde daher zum Kleinen Satz von Fermat zurückgehen in der Form $\begin{eqnarray*} m^p\equiv m\bmod p \end{eqnarray*}$ für alle $\begin{eqnarray*} m \end{eqnarray*}$ :

Aus dem folgt induktiv unmittelbar auch $\begin{eqnarray*} m^{k(p-1)+1}\equiv m\bmod p \end{eqnarray*}$ für alle $\begin{eqnarray*} k\geq 1 \end{eqnarray*}$ .

a) $\begin{eqnarray*} p=2 \end{eqnarray*}$ und $\begin{eqnarray*} k=12 \end{eqnarray*}$ ergibt dann $\begin{eqnarray*} m^{13}\equiv m\bmod 2 \end{eqnarray*}$ .

b) $\begin{eqnarray*} p=5 \end{eqnarray*}$ und $\begin{eqnarray*} k=3 \end{eqnarray*}$ ergibt dann $\begin{eqnarray*} m^{13}\equiv m\bmod 5 \end{eqnarray*}$ .

Beides zusammen ergibt das geforderte $\begin{eqnarray*} m^{13}\equiv m\bmod 10 \end{eqnarray*}$ für alle $\begin{eqnarray*} m \end{eqnarray*}$ .

P.S.: Versucht man, diese zweite Variante des Kleinen Fermat auf den Satz von Fermat-Euler zu übertragen in dem Sinne

$\begin{eqnarray*} m^{k\varphi(n)+1}\equiv m\bmod n \end{eqnarray*}$ für alle positiven ganzen Zahlen $\begin{eqnarray*} k,m,n \end{eqnarray*}$ ,

dann stellt man schnell die Falschheit dieser Aussage fest, z.B. für $\begin{eqnarray*} m=p,n=p^2 \end{eqnarray*}$ . Kann man jedoch zusätzlich die Quadratfreiheit von $\begin{eqnarray*} n \end{eqnarray*}$ voraussetzen, ist die Aussage hingegen richtig.

16.01.2021, 21:19

Leopold

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Wenn ich so denn Thread durchgehe, dann wurde bisher nur $\begin{eqnarray*} m^{13}\equiv m\bmod 10 \end{eqnarray*}$ für die $\begin{eqnarray*} m \end{eqnarray*}$ bewiesen, die teilerfremd (!) zu 10 sind, denn nur für die gilt die benutzte Aussage $\begin{eqnarray*} m^{\varphi(10)} = m^4\equiv 1\bmod 10 \end{eqnarray*}$ . geschockt

Wer (sorgfältig) lesen kann, ist klar im Vorteil ... Freude

Spätestens beim Beispiel mit der 4 hätte es mir eigentlich auffallen müssen. Hammer

16.01.2021, 21:42

HAL 9000

Auf diesen Beitrag antworten »

Weil mir das mit der 13 so gut gefällt, erweitere ich die Aussage mal noch zu $\begin{eqnarray*} m^{13}\equiv m\bmod 2730 \end{eqnarray*}$ für alle $\begin{eqnarray*} m \end{eqnarray*}$ . Augenzwinkern

17.01.2021, 14:52

Riesenfaultier

Auf diesen Beitrag antworten »

Hallo Ihr Beiden,

Vielen Dank für die ausführliche Erklärung.

Eine Sachen die ich leider noch nicht ganz verstehe.

Bei dem Beweis von Hal 9000 splitten wir den Modulus in dessen Primfaktoren, um anschließend den Beweis via den kleinen Satz von Fermat anzutreten. Leider erschließt sich für mich jetzt nicht ganz was hierbei den Unterschied bzgl. der Teilerfremdheit angeht und warum diese bei den Berechnungen mit 2 und 5 für alle Zahlen gilt, obwohl doch alle 10er Schritte nicht Teilerfremd der beiden Modulo sind?

Entschuldigt bitte falls dies dumme Fragen sind, ich versuche das ganze nur zu verstehen und komme mit der Lektüre und den Videos leider nicht mehr weiter.

17.01.2021, 18:00

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Ich würde daher zum Kleinen Satz von Fermat zurückgehen in der Form $\begin{eqnarray*} m^p\equiv m\bmod p \end{eqnarray*}$ für alle $\begin{eqnarray*} m \end{eqnarray*}$ :

Aus dem folgt induktiv unmittelbar auch $\begin{eqnarray*} m^{k(p-1)+1}\equiv m\bmod p \end{eqnarray*}$ für alle $\begin{eqnarray*} k\geq 1 \end{eqnarray*}$ .

Nochmal: Das gilt (im Unterschied zu Euler-Fermat) für alle $\begin{eqnarray*} m \end{eqnarray*}$ . Und bei a),b) wird das ja nur für konkrete p,k genutzt, also gelten auch die für alle $\begin{eqnarray*} m \end{eqnarray*}$ . Was willst du denn noch als Erklärung?

Zitat:

Original von Riesenfaultier
obwohl doch alle 10er Schritte nicht Teilerfremd der beiden Modulo sind?

Ich habe nicht die mindeste Ahnung, was diese wirren Worte aussagen sollen. Erstaunt1

17.01.2021, 20:44

Riesenfaultier

Auf diesen Beitrag antworten »

Hallo,

Vielen dank erstmal für die Arbeit die du dir hier antust, selbst bei den wirren Fragen.

Die Frage was bei mir aufkam, warum die Antwort von Leopold nur für m welche Teilerfremd zu 10 sind gelten und weshalb dies bei deiner Form nicht so ist.

Der Hinweis mit den "im Unterschied zu Euler-Fermat" hat mir jetzt den Knoten gelöst.

Da das Phi(m) die Anzahl der Teilerfremden Zahlen im Wertebereich angibt, bewies ich bzw. Leopold mit dem Euler Fermat nur die Teilerfremden Werte. (1,3,7,9)

Durch den kleinen Satz von Fermat über die beiden Werte kann ich aber eine allgemein gültige Aussage bzgl. der Primzahlen treffen.
Da diese Wiederum zusammen unser gesuchtes Mod 10 ergeben kann ich dies also als w.A. interpretieren?

Bzgl. der wirren frage.....ich war hierbei verwirrt da Leopold geschrieben hat, dass es ihm spätestens bei der 4 auffallen hätte sollen, jedoch ich nicht nachvollziehen konnte weshalb das so ist, da
$\begin{eqnarray*} 4^{13} mod 10 = 4 \end{eqnarray*}$
mMn. eine korrekte Aussage ist. Daraus leitete ich fälschlicherweise ab, dass ich wenn ich bei deinen Gleichnungen die 10 einsetze kein korrektes Ergebnis bekomme.

Entschuldige bitte falls dies wieder verwirrend geschrieben war.

lg.

Neue Frage »

Antworten »

Satz von Euler-Fermat

Verwandte Themen