Beweis für eine Kongruenzgleichung gesucht |
25.06.2019, 20:23 | blackdrake | Auf diesen Beitrag antworten » | |||||
Beweis für eine Kongruenzgleichung gesucht ich suche einen Beweis für folgende Theorie: Gegeben ist Theorie: Es gibt für alle ein Tupel (mit ), für das diese Formel erfüllt ist. Ich habe ein kleines Python-Programm geschrieben, und es scheint wirklich so zu sein, aber mich würde sehr der mathematische Beweis interessieren. Ich wäre sehr dankbar für einen Beweis. Meine Hochschulmathematik-Kenntnisse sind über die Jahre ziemlich "eingestaubt". Hintergrund: Eine Zahl ist "unsterblich" mit Potenz "p" und Basis "b", wenn in Basisnotation der Basis "b" auf "n" endet. Beispiel: 625 ist unsterblich mit Potenz 2 und Basis 10, da (auf 625 endet) Die Gleichung ist: Meine Theorie ist, dass jede Zahl "n" in irgendeiner Basis "b" und Potenz "p" unsterblich ist. Beispiel: Die Zahl 26036 ist unsterblich mit Basis 165 und Potenz 111. |
|||||||
25.06.2019, 21:59 | Finn_ | Auf diesen Beitrag antworten » | |||||
Sei . Nach dem Satz von Euler-Fermat gilt dann Demnach gilt auch Ist nun eine Primzahl, die nicht als Primfaktor in vorkommt, dann kommt auch die Primzahlpotenz nicht als Primfaktor in vor. Ergo muss sein, sofern ist. Man bekommt dann . |
|||||||
26.06.2019, 00:12 | Finn_ | Auf diesen Beitrag antworten » | |||||
Es stellt sich noch die Frage, wie man eine möglichst kleine Potenz findet. Setzen wir mal voraus, dass ist. Dann gilt auch wobei nun aber die kleinste Zahl mit dieser Eigenschaft ist, wobei vorausgesetzt wird. Hierbei ist die Carmichael-Funktion. Der Wert ist in einigen Fällen kleiner als . In deinem Beispiel ist und . Es ergibt sich . Man erhält und . Es gilt aber auch schon , woraus dann folgt. Das ist so, weil bei die kleinste Zahl gefragt ist, so dass die Kongruenz für alle gilt. Wir haben aber nur ein spezielles vorliegen. Daher kann es auch noch kleinere Potenzen als geben. Es ist nun so, dass mit die Zahl ein Element der Einheitengruppe ist. Die kleinste Zahl mit modulo ist gleichbedeutend mit der Ordnung des Gruppenelements . Das wiederum ist gleichbedeutend mit der Ordnung der zyklischen Gruppe . Da eine Untergruppe von ist, muss nach dem Satz von Lagrange die Zahl ein Teiler von sein. Man berechnet nun die Teilerliste von und sucht nach dem ersten Teiler , für welchen modulo ist.
|
|||||||
26.06.2019, 00:46 | blackdrake | Auf diesen Beitrag antworten » | |||||
Hallo Finn, vielen Dank für diesen schönen Beweis! Den eigentlichen Beweis (erste Antwort) habe ich gut verstanden. Die zweite Antwort muss ich mir noch genauer anschauen, die ist etwas komplexer. Ich mache mir wegen einer großen Potenz eigentlich weniger Sorgen. Super wäre es jedoch, wenn man die Basis auf 2..36 beschränken könnte, sodass man die Zahl mit dem Alphabet 0..9,A..Z notieren kann. Kann man mit einer auf 2..36 beschränkten Basis für jede Zahl ein finden? |
|||||||
26.06.2019, 02:30 | Finn_ | Auf diesen Beitrag antworten » | |||||
Das läuft auf die Frage hinaus, ob die Kongruenz für eine Lösung besitzt. Dann gilt . Die Kongruenz besagt nun aber, dass im Restklassenring ein multiplikativ inverses Element mit und besitzen soll. Gemäß dem Satz zum erweiterten euklidischen Algorithmus besitzt genau dann multiplikativ inverse Elemente, wenn ist. Nun ist es aber so, dass die Potenz der Zahl ist, dass also verlangt wird, denn jeder Primteiler von wird auch in enthalten sein. Gibt es ein Gegenbeispiel? Eine entsprechend hoch zusammengesetzte Zahl hat alle Zahlen 2, 3, ..., 36 in ihrer Teilerliste. Man braucht bloß zu berechnen und bekommt 144403552893600. Eigentlich genügt es schon, wenn jeden Primteiler in 2, 3, ..., 36 einmal enthält. Man findet 200560490130. Für diese Zahl sollte die Kongruenz unter der Einschränkung der Wahl der Basis unlösbar sein. Sofern mir jetzt nicht irgendwo ein Fehler unterlaufen ist. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|