Kleiner Satz von Fermat

Aufrufe: 624     Aktiv: 31.01.2021 um 17:19
0

Der kleine Satz von Fermat besagt (soweit ich das verstanden habe), wenn modul und Repräsentant der Restklasse teilerfremd sind, dann ist der Rest der Potenz des teilerfremden Repräsentanten der Restklasse und des Moduls gleich 1 (z.B. 2^x => 4, 16, 256) (bei mod 3), wenn ich dies jedoch beispielweise mit der Z15 versuche, dann wäre theoretisch 13 (habe einen höheren Wert genommen) teilerfremd zu 15, der Rest der 2. Potenz jedoch 4 (gleiches bei, bei 2, oder müsste ich sowieso mit dem höchsten Potenz-Repräsentanten anfangen müssen (bei 15 => 2^3 (8(würde wieder nicht funktionieren)), der innerhalb der Restklasse liegt? Da es mit 4 funktionieren würde (mit 8 scheinbar nicht), mit 13 jedoch sowieso nicht.

 

Vielen Dank schon einmal für eure Hilfe :)

Diese Frage melden
gefragt

Auszubildender, Punkte: 148

 
Ich glaube ich habe die Lösung schon, ich muss den Repräsentanten der Restklasse solange potenzieren (in einem minimalen Bereich) bis ich bei dem Wert der Identität angelangt bin (2^(4)= 16 => d.h. 4 wäre die Ordnung) jetzt könnte man theoretisch doch 16 nehmen ((2^(4))^(x)=> und egal was man hierbei für x einsetzt der Rest zum Modul wäre immer 1?   ─   infomarvin 30.01.2021 um 18:46
Kommentar schreiben
1 Antwort
1

Ich bin mir nicht ganz sicher, ob ich verstehe, was du meinst. Der kleine Satz von Fermat sagt, dass für ein Primzahl \(p\) und \(a\in\mathbb Z\setminus\{0\}\) stets \(a^{p-1}\equiv1\mod p\) gilt. Dies kann man verallgemeinern, z.B. gilt für beliebiges \(n\in\mathbb N\) stets \(a^{\varphi(n)}\equiv 1\mod n\), wobei \(\varphi\) die Eulersche \(\varphi\)-Funktion ist. Dies folgt sofort aus dem kleinen Satz von Fermat und dem Chinesischen Restsatz.

Insbesondere gibt es keinen Grund anzunehmen, dass \(13^2\equiv1\mod 15\) wäre. Wegen \(\varphi(15)=8\) gilt allerdings \(13^8\equiv1\mod15\).

Zu deinem Kommentar: Natürlich ist \(16^x\equiv 1\mod 15\) für alle \(x\), denn \(16\equiv 1\Longrightarrow 16^x\equiv 1^x\equiv 1\mod 15\). Das hat aber nichts mit dem Satz von Fermat zu tun.

Wie gesagt, ich habe nicht 100% verstanden, was deine Frage ist. Schreib also gern noch einen Kommentar, falls weiterer Klärungsbedarf besteht.

Diese Antwort melden
geantwortet

Punkte: 11.27K

 
Danke, schaue mir mal das zuerst an :) Die Euler'sche Phi Funktion (abgesehen von dem teilerfremden Output) ja demnach (soweit ich das verstanden habe) nicht anderes als dass was ich gemeint habe, oder? Prinzipiell könnte man ja für p (mod p) jede Primzahl einsetzen, und für den Exponenten jede beliebige Zahl? Da gilt (tut mir leid beherrsche kein Latex) a kongruent b mod p <=> a kongruent 1 mod p, dass a^(x) kongruent 1^(x) mod p ist, also wäre ja x unabhängig von p, dass phi(prim)= prim - 1 ist habe ich verstanden, aber inwieweit wäre es relevant eben diesen Output bei a^(p-1) einzusetzen, da soweit ich verstanden habe x ja unabhängig von p ist, solange a kongruent 1 ist? (also grundlegend verstehe ich den Sinn des Exponenten bei a nicht, wenn a sowieso kongruent 1 zu mod ist )
Ich wollte mich allgemein einmal für deine wiederkehrende und Hilfe (und das kostenlos :D) bedanken (werde dich, wenn ich endlich mehr Zeit habe (nach 19.2. :D) auf jeden Fall einmal entsprechend bewerten - vielen Dank :)   ─   infomarvin 31.01.2021 um 16:55
Für den Exponenten kann man eben nicht jede beliebige Zahl einsetzen, solange \(a\not\equiv 1\). Zum Beispiel ist \(2^n\not\equiv1\mod 5\) für \(n=1,2,3\), aber nach dem kleinen Satz von Fermat gilt eben \(2^4\equiv 1\mod 5\)   ─   stal 31.01.2021 um 17:02
Ok jetzt habe ich es verstanden, ich bin grundsätzlich davon ausgegangen, dass a sowieso kongruent 1 sein muss, bevor man den Output überhaupt anwendet, so macht es Sinn ich nehme eine Repräsentanten der Restklasse != 1,0,m einer Primzahl 1 < repräsentant < m und kann diesen Repräsentanten mit z.B. Phi(Primzahl)= Primzahl - 1 => a^(Primzahl - 1) exponieren, und der Wert ist immer kongruent der Restklasse 1, danke :)   ─   infomarvin 31.01.2021 um 17:19

Kommentar schreiben