Diskussion:Eulersche Pseudoprimzahl

Definition

Wenn $a^{(n-1)/2}\equiv \pm 1\mod n$ gilt, dann folgt automatisch

• $\operatorname {ggT} (a,n)=1$
• $a^{n-1}\equiv 1\mod n$

Wieso man die Basis auf $1\leq a\leq n$ einschränken sollte, ist mir nicht klar, die englische WP macht das jedenfalls nicht. Ggf. Belege.--Gunther 19:06, 16. Mai 2006 (CEST)

Es geht nicht um $1\leq a\leq n$ sondern um $2\leq a\leq n-2$. Klar sind auch Basen größer $n\$ zulässig. Nur es darf keine Basis der Form $a=bn+1$ oder der Form $a=bn-1$ sein. Das wird aber komplizierter zu erklären sein. --Arbol01 19:11, 16. Mai 2006 (CEST)

Hier noch eine Quelle:

"Prime Numbers", Richard Crandall & Carl Pomerance, Springer Verlag, ISBN 0-387-25282-7

Seite 132, Chapter 3 Recognizing primes and comosites, Theorem 3.4.2 und Algorithm 3.4.3

--Arbol01 19:21, 16. Mai 2006 (CEST)

Selbes Buch (allerdings erste Auflage), Aufgabe 3.21 auf S. 154 definiert eulersche Pseudoprimzahlen zur Basis $a$ als Zahlen $n$, für die $(a,n)=1$ gilt und $a^{(n-1)/2}\equiv (a/n)\mod n$ (Jacobi-Symbol), keine weiteren Einschränkungen an $a$.--Gunther 19:35, 16. Mai 2006 (CEST)

Ja, weil eine eulersche Pseudoprimzahl eine fermatsche Pseudoprimzahl sein muß. Das impliziert die Einschränkung. --Arbol01 20:38, 16. Mai 2006 (CEST)

Das steht da nicht.--Gunther 21:43, 16. Mai 2006 (CEST)

Muß das erst da stehen? Wenn für eine fermatsche Pseudoprimzahl $n\$ gilt, das wenigstens eine Basis $a\$ mit $2\leq a\leq n-2$ existieren muß, so daß $a^{n-1}\equiv 1\mod n$ zutrifft, und für eine eulersche Pseudoprimzahl gilt, daß sie eine fermatsche Pseudoprimzahl ist, dann muß zwangsläufig gelten, das auch für eine eulersche Pseudoprimzahl diese Einschränkung gilt.

Wenn das nicht im Buch steht, liegt das auch an der etwas anderen Motivation. Die Motivation des Buches liegt ja vorwiegend auf der Primzahl, und mit welchen Algorithmen Primzahlen von Nichtprimzahlen unterschieden werden können. --Arbol01 21:53, 16. Mai 2006 (CEST)

Habe mal zwei verschiedene Definitionsvarianten aufgetrennt und mit entsprechenden Quellen versehen. Leider gibt es hauptsächlich Quellen zu den Euler-Jacobi-ΨPZ, um die es ja weiter unten gar nicht geht. Wenn Du weitere Varianten (z.B. mit $2\leq a\leq n-2$) im Artikel unterbringen willst, dann bitte mit Beleg.--Gunther 01:42, 17. Mai 2006 (CEST)