Benutzer:Arbol01/Archiv nützlicher Dialoge

Der kleine Fermasche Satz und die Lucas-Folge

Hier beglücke ich die Mathematikergemeinschaft mal wieder mit einem Geistesblitz (hat lange genug gedauert). Wie ich schon weiter oben schrieb, hatte ich festgestellt, das die Lucas-Folge $V(3,2)=2^{n}+1^{n}$ in bezug auf die Eigenschaften von Primzahlen äquivalent zu $2^{n}-2$ ist.

Für jede Primzahl n gilt: $V_{n}(P,Q)\equiv P\mod n$ (Lucas-Folge)

Für jede Primzahl n gilt: $2^{n}-2\equiv 0\mod n$ (kleiner Fermatscher Satz)

So, nun habe ich mich gefragt, ob sich das verallgemeinern läßt. Ob es also für jede Basis a mit $a^{n}-a\equiv 0\mod n$ eine passende Lucas-Sequenz gibt, und ob für diese Lucas-Folgen die glechen Pseudoprimzahlen auftauchen, wie für den jeweilig entsprechenden kleinen Fermatschen Satz.

$V_{(}a+1,a)=a^{n}+1^{n}$

$a^{n}+1^{n}\equiv (a+1)\mod n$ - (a+1)

$a^{n}-a\equiv 0\mod n$

So, jetzt meine Frage: Wo bringt man so etwas eher unter? Im kleinen Fermatschen Satz, bei den Fermatschen Pseudoprimzahlen, bei den Lucas-Folgen, oder wo?

Ach ja, ich habe zwei Stichproben bezüglich der Pseudoprimzahlen gemacht: 91 ist pseudoprim bezüglich $V_{91}(4,3)$ und 15 ist pseudoprime bezüglich $V_{15}(12,11)$ --Arbol01 12:34, 20. Jul 2005 (CEST)

Wenn Du Dir das nur selbst ausgedacht und nicht irgendwo gefunden hast, ist es Theoriefindung und nach WP:WWNI hier falsch.--Gunther 12:55, 20. Jul 2005 (CEST)

Ausgedacht wäre wohl übertrieben. Ich habe mit der Lucas-Folge herumgespielt. Klar grenzt das an die Theoriefindung. Ich kann allerdings noch warten. Ich habe das Ganze an Herrn Gerard Michon gesendet, mal sehen, was er dazu sagt. Aber, wenn Du mal versuchen würdest, meine Gedankengänge nachzuvollziehen? --Arbol01 13:05, 20. Jul 2005 (CEST)

Es geht um die Aussage $p\mid V_{p}(a+1,a)-V_{1}(a+1,a)\iff p\mid a^{p}-a$? Allgemein sollte eine Aussage bei dem wichtigsten Begriff stehen, zu dem sie noch wesentlich beiträgt. Das wäre mMn in diesem Fall Lucas-Folge; den Begriff der Fermat-Pseudoprimzahlen würde ich für wichtiger halten, aber die Aussage trägt nicht wesentlich zu ihrem Verständnis bei.--Gunther 13:20, 20. Jul 2005 (CEST)

Carmichael-Funktion und Carmichael-Zahl

Für eine natürliche Zahl n gilt $a^{\lambda (n)}\equiv 1\mod n$ für jede natürliche Zahl a mit $1\leq a<n$ die zu n teilerfremd sind.

Eine Carmichael-Zahl ist eine zuammengesetzte, natürliche Zahl n für die gilt, das für jede natürliche Zahl a mit $1\leq a<n$ die zu n teilerfremd $a^{n-1}\equiv 1\mod n$ ist.

Mein Verdacht ist nun, das eine zusammengesetzte, natürliche Zahl n nur dann eine Carmichael-Zahl ist, wenn (n-1) ein vielfaches von $\lambda (n)$ ist, bzw. wenn $\lambda (n)$ die Zahl (n-1) teilt. --Arbol01 14:41, 2. Sep 2005 (CEST)

Ist $n$ eine Carmichael-Zahl und $0<r<\lambda (n)$ der Rest von $n-1$ modulo $\lambda (n)$, so gilt $a^{r}\equiv 1\mod n$ für jeden teilerfremden Rest $a$, im Widerspruch zur Definition von $\lambda (n)$.--Gunther 14:45, 2. Sep 2005 (CEST)

Soll das jetzt Positiv oder negativ gemeint sein? 560 / 80 = 7 ; 1104 / 48 = 23 ; 1728 / 36 = 48 ; 2464 / 112 = 22

So weit ich sehen kann, gibt es bei Carmichaelzahlen keine rest r wenn man n-1 / lambda(n) teilt. --Arbol01 16:19, 2. Sep 2005 (CEST)

Nachtrag: Ich sehe mal die Aussage als Bestätigung an, da die Carmichael-Zahl als Ergebnis die kleinste narürliche Zahl m zurückliefert, für die $a^{m}\equiv 1\mod n$ gilt. Es kann also keine kleinere Zahl r mehr geben. --Arbol01 16:25, 2. Sep 2005 (CEST)

Ja, genau. Wäre der Rest $r$ positiv, so ergäbe sich der o.g. Widerspruch.--Gunther 16:57, 2. Sep 2005 (CEST)

Noch einen kleinen Nachschlag: Wenn $c-1=\lambda (c)\cdot d$ ist, was ist dann $d\$. Ich vermute, folgende Formel ist gültig: $d=\operatorname {ggT} \left({\frac {c-1}{p_{1}-1}},{\frac {c-1}{p_{2}-1}},...,{\frac {c-1}{p_{n}-1}}\right)$ für die Carmichaelzahl $c=p_{1}\cdot p_{2}\cdot ...\cdot p_{n}$. --Arbol01 16:50, 3. Sep 2005 (CEST)

Ja, aus $\lambda (c)=\operatorname {kgV} \{p_{i}-1\mid i=1,\ldots ,n\}$ folgt

$d={\frac {c-1}{\operatorname {kgV} \{p_{i}-1\mid i=1,\ldots ,n\}}}=\operatorname {ggT} {\Big \{}{\frac {c-1}{p_{i}-1}}\,{\Big |}\,i=1,\ldots ,n{\Big \}}.$

--Gunther 17:12, 3. Sep 2005 (CEST)

Änderungen in Primzahl

Keine Kritik zu deiner Änderung. Blos eine Frage:

Hat deine Änderung auch mit $V_{p}(a+1,a)-V_{1}(a+1,a)=a^{p}-a\$ zu tun? Keine Äquivalenz, sondern echte Gleichheit (ich habe mir in www.matheplanet.de die Gleichheit beweisen lassen, und kann sie nachvollziehen). --Arbol01 21:09, 13. Jan 2006 (CET)

Eher direkt mit $V_{n}(a+1,a)=a^{n}+1$, also damit, dass die Folgen im wesentlichen die Form $a_{n}=\lambda ^{n}$ haben. Wenn $\lambda$ keine ganze Zahl mehr ist, kann man den kleinen Fermat nicht mehr einfach so anwenden, daher die Komplikationen.--Gunther 21:39, 13. Jan 2006 (CET)

Weiteres

Bevor Ihr da noch mehr Energie in die Frage investiert, ob nun 1+3 oder 5+7 das geeignetere Gegenbeispiel ist, mal grundsätzlich: 1. Ist diese falsche Aussage nicht viel zu offensichtlich falsch, als dass man das erwähnen müsste? Es gibt noch viel mehr falsche Aussagen, die man erwähnen könnte... 2. Welche Anwendungen gibt es für die richtige Aussage? Es gibt noch mehr ziemlich triviale Aussagen über Primzahlen (z.B. ist die Differenz zweier Quadratzahlen höchstens dann eine Primzahl, wenn dazwischen keine weitere Quadratzahl liegt).--Gunther 23:37, 17. Jan 2006 (CET)

Naja, geeignet sind eigentlich beide Beispiele nicht! 1+3 micht, weil 1 das "neutrale Element" ist, und 5+7 nicht, weil es sich bei beiden Zahlen um Primzahlen handelt.

Ich werde das ganze in meinem Parallel-Projekt Primzahlen in Wikibooks noch ausführlicher abhandeln. Dort nicht direkt unter Eigenschaften, sondern unter der Eigenschaft das eine Primzahl nur durch 1 und sich selbst teilbar ist. AFAIK gehören beide Dinge zusammen, bzw. ist das eine eine Folge des anderen (Widerspruch?).

Zu 1.: Ich meine nicht, das diese falsche Aussage viel zu offensichtlich ist, wo Leute die 1 immer noch für eine Primzahl halten. --Arbol01 23:48, 17. Jan 2006 (CET)

Ach ja, zu 2.: Theoretisch kann man, Analog zum naiven Primzahltest einen naiven Primzahltest benutztn, der die additiven Eigenschaften verwendet. Das mag zwar etwas esoterisch sein, aber nicht Abwegig. --Arbol01 23:50, 17. Jan 2006 (CET)

Zum Gegenbeispiel: Jede natürliche Zahl (außer 1) lässt sich als Summe zweier teilerfremder Zahlen darstellen. Wenn man die 1 als Summand ausschließt, ist es für jede natürliche Zahl $\geq 7$ möglich (sogar mit einer Primzahl als einem der Summanden). Irgendwelche großen Zahlen suggerieren, dass es sich um ein seltenes Phänomen handelt.

Zu Deinem Primzahltest: Das ist wegen $\operatorname {ggT} (a,b)=\operatorname {ggT} (a-b,b)$ eine triviale Umformung des "Primzahltestes", der $\operatorname {ggT} (a,p)=1$ für $a=1,\ldots ,p-1$ überprüft. Diese letztere Aussage ist erwähnenswert (endliche Körper usw.), das fehlt momentan.--Gunther 00:11, 18. Jan 2006 (CET)

Danke für die indirekte Bestätigung meiner Vermutung (siehe etwas weiter oben). --Arbol01 00:17, 18. Jan 2006 (CET)

Kettenbruch und spezielle Folgen

Das der Grenzwert des Quotienten zweier Folgen der Fibonacci-Folge, bzw. der Lucas-Folge, der goldene Schnitt ist, und das der nicht abbrechende Kettenbruch [1;1,1,1,1,...] ist, sollte kein geheimnis sein. Und in der, zu der Fibonacc-Folge und Lucas-Folge zugehörigen quadratischen Gleichung $a={\frac {P+{\sqrt {P^{2}-4Q}}}{2}}$ mit $P=1\$ und $Q=-1\$ ist die Lösung $a={\frac {1+{\sqrt {5}}}{2}}$. Also der goldene Schnitt.

Nun wollte ich wissen, was der Grenzwert des Quotienten zweier aufeinanderfolgender Glieder der Pell-Folge ist. Die Antwort war $1+{\sqrt {2}}$. Das entspricht wiederum genau der Lösung $a={\frac {P+{\sqrt {P^{2}-4Q}}}{2}}$ für die Pell-Folge. Ich hätte es eigentlich wissen sollen!

Noch erstaunter war ich, als ich den Kettenbruch berechnet habe. Das Ergebnis ist [2;2,2,2,2,2,...]. Nun meine Frage: Ist bei den Kettenbrüchen die aus den Grenzwerten zweier aufeinanderfolgender Glieder der allgemeinen Lucas-Folgen resultieren damit zu rechnen, das häufiger [n;n,n,n,n,...] auftauchen? --Arbol01 00:59, 28. Mär 2006 (CEST)

[n;n,n,n,...] ist die positive Lösung der quadratischen Gleichung $x^{2}-nx-1=0$, die den Parametern $P=n$ und $Q=-1$ entspricht.--Gunther 15:17, 28. Mär 2006 (CEST)

Aaahhh, danke --Arbol01 16:49, 28. Mär 2006 (CEST)

Fermatsche Pseudoprimzahlen nach Lehmer

Von dem Mathematiker Lehmer stammt folgende Konstruktionsvorschrift für fermatsche Pseudoprimzahlen:

Man nimmt eine natürliche Zahl k mit k >= 5. Dann berechnet man 2^k und bestimmt die Faktoren von 2^k-1 und 2^k+1. Das Produkt aus je einem der beiden Faktoren ist dann eine fermatsche Pseudoprimzahl zur Basis 2^k.

Beispiel:

k=7 ; 2⁷ = 128 ; 127 = 127 ; 129 = 3*43 ; 43*127 = 5461

5461 ist also eine fermatsche Pseudoprimzahl zur Basis 128 (unter anderem).

Nun ist mir eine Idee gekommen, die nur bedingt mit dem oben Beschriebenen zu tun hat. Zu einer fermatschen Pseudoprimzahl q sind bestimmte Basen a_n bekannt. Wenn für ein bestimmtes n folgendes gilt: $2^{n}\equiv a_{n}\mod q$, ist q dann eine fermatsche Pseudoprimzahl zur Basis 2ⁿ. --Arbol01 23:46, 20. Jun 2006 (CEST)

Also wenn $q$ eine ΨPZ zur Basis $a$ ist, und $a\equiv b\mod q$, dann ist $q$ nach den elementaren Rechenregeln für Kongruenzen auch eine ΨPZ zur Basis $b$. Das kann irgendwie nicht Deine Frage gewesen sein, oder?--Gunther 00:05, 21. Jun 2006 (CEST)

Naja, eigentlich schon. Ich weiß, eigentlich eine blöde Frage, aber manchmal ist man etwas unsicher. Ich knabbere etwas an dem Schema von Lehmer. Wie kann es sein, das diese Zahlen ausgerechnet pseudoprim zur Basis 2^k sind. Sie sind es, aber warum. --Arbol01 00:12, 21. Jun 2006 (CEST)

Wenn $q\mid 2^{k}-1$ und $r\mid 2^{k}+1$, dann ist $qr\mid (2^{k}-1)(2^{k}+1)=2^{2k}-1$, also $(2^{k})^{qr-1}=(2^{2k})^{(qr-1)/2}\equiv 1\mod (qr)$.--Gunther 00:39, 21. Jun 2006 (CEST)

Vielen dank für die erschöpfende Antwort. Warum habe ich das nicht gesehen? Wenn man es sieht, ist es eigentlich ganz einfach. --Arbol01 02:02, 21. Jun 2006 (CEST)