WYA:Offene Fragen bei den Pseudoprimzahlen

From Citizendium, the Citizens' Compendium
Jump to: navigation, search

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 durch teilbar ist. Ist eine Primzahl, so trifft es zu, das durch teilbar ist. Unglücklicherweise gibt es auch zusammengesetzte Zahlen , für die durch 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 ist dann eine fermatsche Pseudoprimzahl, wenn es wenigstens eine natürliche Zahl gibt, für die gilt ist durch teilbar, oder besser ist durch teilbar. Man sagt dann, Die Zahl ist eine fermatsche Pesudoprimzahl zur Basis .

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 ist das Produkt der beiden Primzahlen und . Wenn wir jeweils ein Vielfaches der einen Primzahl: und ein Vielfaches der anderen Primzahl: finden, so das der Betrag der Differenz gleich 2 ist, dann ist die zwischen und liegende Zahl eine Basis zu der die ungerade, zusammengesetze Zahl pseudoprim, im Sinne von ist durch teilbar, ist. Dabei gibt es nicht nur eine Basis , sondern die auf die Zahl trifft das gleiche zu. Auch sie liegt zwischen Vielfachen der Primzahlen und .

Nebenbei gesagt sind alle Zahlen der Form und ebenfalls Basen, zu denen die ungerade, zusammengesetze Zahl pseudoprim, im Sinne von ist durch 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 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.