User:Karsten Meyer/Offene Fragen bei den Pseudoprimzahlen

The account of this former contributor was not re-activated after the server upgrade of March 2022.

Einführung: Was ist eine Pseudoprimzahl

Wenn man von einer natürlichen Zahl, die größer als 1 ist, wissen möchte, ob sie eine Primzahl ist oder nicht, dann kann man zum Beispiel testen, ob die Zahl durch eine andere Zahl als 1 oder sie selbst teilbar ist. Je größer ide zu testende Zahl ist, desto mehr Zeit wird benötigt, die Zahl auf Teilbarkeit zu testen. Deswegen hat man versucht, andere, schnellere Wege zu finden. Einer dieser Wege ist zu testen, ob $a^{n}-a\$ durch $n\$ teilbar ist. Ist $n\$ eine Primzahl, so trifft es zu, das $a^{n}-a\$ durch $n\$ teilbar ist. Unglücklicherweise gibt es auch zusammengesetzte Zahlen $n\$, für die $a^{n}-a\$ durch $n\$ teilbar ist. Solche Zahlen gehören zu den fermatschen Pseudoprimzahlen. Es gibt auch noch andere Pseudoprimzahlen.

Was macht eine Zahl zu einer fermatschen Pseudoprimzahl?

Eine zusammengesetzte Zahl $n\$ ist dann eine fermatsche Pseudoprimzahl, wenn es wenigstens eine natürliche Zahl $a\$ gibt, für die gilt $a^{n}-a\$ ist durch $n\$ teilbar, oder besser $a^{n-1}-1\$ ist durch $n\$ teilbar. Man sagt dann, Die Zahl $n\$ ist eine fermatsche Pesudoprimzahl zur Basis $a\$.

Wie findet man nun solche Basen zu einer Pseudoprimzahl?

Man kann zum Beispiel eine Zahl auf alle potentielle Basen testen:

/* REXX-Programm */
say 'Only a Library!'
exit 1
/* */
/* */
m_u: procedure
  arg a,l,m
/* initialisierung */
  as = a
  ai = a
  li = (l-1)
  DO li
    a = a * ai
    a = a // m
  END
return a

mod_up.r

Ein Quellcode, um fermatsche Pseudoprimzahlen zu finden:

/* Ein REXX-Programm */

call load 'mod_up.r'
anzfpspr=0
do i = 2 to 99999
  fpsprb.i = " "
  t=0
  t2=0
  do i2 = 2 to (i-2)
    call m_u i2, (i-1), i
    pt = result
    if (pt = 1) then do
                        t = 1
                        fpsprb.i2 = fpsprb.i2||i||", "
    end
    if (pt > 1) then t2 = 1
  end
  tg = t + t2
  if (tg = 2) then do
                     anzfpspr = anzfpspr + 1
                     ausgabe = "fpspr."||anzfpspr||" = "||i
                     say ausgabe
                     lineout("epspr_var.txt",ausgabe)
  end
end
lineout("fpsprb_table2.txt","{| {{prettytable}")
do i = 2 to 99999
  ausgabe = "|"||i||" ||"||fpsprb.i||"@"
  say ausgabe
  lineout("fpsprb_table2.txt",ausgabe)
  lineout("fpsprb_table2.txt","|-")
end

Das hier angegebene Programm gibt alle fermatschen Pseudoprimzahlen zwischen 2 und Obergrenze, mitsamt den dazugehörigen Basen, aus:

15	4, 11
21	8, 13
25	7, 18
28	9, 25
33	10, 23
35	6, 29
39	14, 25
45	8, 17, 19, 26, 28, 37
49	18, 19, 30, 31
51	16, 35
52	9, 29
55	21, 34
57	20, 37
63	8, 55
65	8, 12, 14, 18, 21, 27, 31, 34, 38, 44, 47, 51, 53, 57
66	25, 31, 37, 49
69	22, 47
70	11, 51
75	26, 49
76	45, 49
77	34, 43
85	4, 13, 16, 18, 21, 33, 38, 47, 52, 64, 67, 69, 72, 81
87	28, 59
91	3, 4, 9, 10, 12, 16, 17, 22, 23, 25, 27, 29, 30, 36, 38, 40, 43, 48, 51, 53, 55, 61, 62, 64, 66, 68, 69, 74, 75, 79, 81, 82, 87, 88
93	32, 61
95	39, 56
99	10, 89
105	8, 13, 22, 29, 34, 41, 43, 62, 64, 71, 76, 83, 92, 97
111	38, 73
112	65, 81
115	24, 91
...	...

Wenn man allerdings die fermatschen Pseudoprimzahlen aufdröselt, und bestimmte, isolierte Formen betrachtet, so gibt es einfachere Wege. So lassen sich zu jeder ungeraden, zusammengestetzten Zahl, die das Produkt von genau zwei Primzahlen ist, sehr leicht zwei Basen finden, zu denen die Zahl pseudoprim ist:

Die ungerade, zusammengesetze Zahl $n\$ ist das Produkt der beiden Primzahlen $p_{1}\$ und $p_{2}\$. Wenn wir jeweils ein Vielfaches der einen Primzahl: $s\cdot p_{1}$ und ein Vielfaches der anderen Primzahl: $t\cdot p_{2}$ finden, so das der Betrag der Differenz $|s\cdot p_{1}-t\cdot p_{2}|$ gleich 2 ist, dann ist die zwischen $s\cdot p_{1}$ und $t\cdot p_{2}$ liegende Zahl eine Basis $a\$ zu der die ungerade, zusammengesetze Zahl $n\$ pseudoprim, im Sinne von $a^{n-1}-1\$ ist durch $n\$ teilbar, ist. Dabei gibt es nicht nur eine Basis $a\$, sondern die auf die Zahl $a_{2}=n-a\$ trifft das gleiche zu. Auch sie liegt zwischen Vielfachen der Primzahlen $p_{1}\$ und $p_{2}\$.

Nebenbei gesagt sind alle Zahlen der Form $k\cdot n+a$ und $k\cdot n+a_{2}$ ebenfalls Basen, zu denen die ungerade, zusammengesetze Zahl $n\$ pseudoprim, im Sinne von $a^{n-1}-1\$ ist durch $n\$ teilbar, ist.

Bei ungeraden, zusammengesetzten Zahlen, die das Produkt von drei oder mehr unterschiedlichen Primzahlen sind, kann man ähnlich wie bei ungeraden, zusammengesetzen Zahlen die nur das Produkt zweier unterschiedlicher Primzahlen sind, vorgehen.

Es gibt mehr als zwei Basen?

Jetzt kommen wir zum ersten Problem: Wir haben gesehen, das wir bei ungeraden, zusammengesetzten Zahlen zwei Basen einfach herausfinden können. Nur, wie ist es, wenn es mehr als die zwei Basen gibt? Beispiel 65. 65 ist das Produkt der zwei Primzahlen 5 und 13. Die zwei Basen, die wir leicht ermitteln können sind 14 und 51. Nun existieren aber unterhalb von 65 genau 14 Basen, zu denen die Zahl 65 pseudoprim ist: (8; 12; 14; 18; 21; 27; 31; 34; 38; 44; 47; 51; 53; 57). Auf welchem Weg könnte man die restlichen 12 Basen bestimmen, ohne die 65 aud den kleinen fermatschen Satz zu testen?

Noch schwieriger ist es bei den Quadratzahlen von Primzahlen. Die starke Pseudoprimzahl $49=7\cdot 7$ hat vier Basen, kleiner 49, zu denen sie Pseudoprim ist: (18; 19; 30; 31), und keine dieser Basen läßt sich nach dem oben beschriebenen Schema herausfinden. Das gilt für alle Quadratzahlen von Primzahlen, die meistens starke Pseudoprimzahlen sind.