3.6 PSEUDOPRIMZAHLEN UND PRIMZAHLTESTS

 

Schon die chinesischen Mathematiker zu Zeiten des Konfuzius (5.Jhd. v.Chr.) beschäftigten sich mit der Frage, ob eine Zahl n, die 2n-1-1 teilt, prim sei. Damit vermuteten sie eine eingeschränkte Umkehrung des kleinen Fermat'schen Satzes.

AUFGABE 3.53 
    Überprüfe, ob n 2n-1-1 teilt für n=2 bis 20.

Die Chinesen und nach ihnen berühmte Mathematiker wie Leibnitz und Euler hielten die Vermutung (mangels Computer?) für richtig. Erst 1819 fand der französische Mathematiker Sarrus (auch ohne Computer!) ein Gegenbeispiel: Für 341=11× 31 gilt 341ï 2340-1. Beweis:

210º 1 mod 11 Þ 2340=(210)34º 134=1 mod 11
230º 1 mod 31 Þ 2340=(230)11× 210º 210=1024º 1 mod 31

AUFGABE 3.54 
    Überprüfe für alle n<50: nï2n-1-1 (geeignetes Programm)

DEFINITION 3.6 
Eine zusammengesetzte Zahl n mit nï 2n-1-1 heißt "Pseudoprimzahl".
(PSP-Zahl)

Bemerkung: Früher wurde im allgemeinen die Bedingung nï 2n-2 für Pseudoprimzahlen verlangt, denn aus nï 2n-2=2× (2n-1-1) folgt auch nï 2n-1-1. Man konnte auf diese Art auch gerade Pseudoprimzahlen finden. (siehe Aufgabe 3.56)

AUFGABE 3.55 
Zeige, dass auch 561, 1105, 1387 und 2047 Pseudoprimzahlen sind.

AUFGABE 3.56 
Es war lange unbekannt, ob es auch gerade Pseudoprimzahlen, also Zahlen mit nï 2n-2, gibt. 1950 entdeckte Lehmer die erste: 161.038=2× 73× 1103. 
Beweise, dass gilt 161.038ï 2161.038-2.
(Hinweis: Beachte, dass 2161038-2=2(2161037-1) ist. Wegen 161037= 32 29× 617 zerfällt der 2. Faktor auf jeden Fall in 29-1, 229-1 und 2617-1. Suche nach Beziehungen dieser Faktoren zu den Primfaktoren von 161038.)

Von Lehmer stammt auch das folgende Primtestverfahren für eine Zahl n unter einer Schranke N: Man schaffe sich eine Liste der PSP-Zahlen <N (was er selbst für N=2× 108 tat); wenn 2n-1 inkongruent 1 mod n, ist n zusammengesetzt - ist aber 2n-1º 1 mod n und nicht in der Liste, so ist n prim. Das Verfahren ist nicht besonders effektiv, so dass wir nicht weiter darauf eingehen werden.

AUFGABE 3.57 
Teste mit den oben angegebenen Zahlen und einigen mehr Lehmers Verfahren.

AUFGABE 3.58 
a) Verifiziere an einigen Beispielen den folgenden Satz von Lehmer:
     p×q ist pseudoprim Û ordp(2)ï q-1 Ù ordq(2)ï p-1
b) Verifiziere an einigen Beispielen den folgenden Satz (auch von Lehmer): 
    z=p1× p2× p3 ist PSP-Zahl Þ

Die Beschäftigung mit PSP-Zahlen wirft die Frage auf, ob die Basis 2 in diesem Zusammenhang eine besondere Rolle spielt oder ob es auch andere Basen b gibt, zu denen es zusammengesetzte Zahlen n>b gibt mit nï bn-1-1 und ggT(n,b)=1. Man spricht dann von PSPb-Zahlen.

  • Beispiel: 1541 ist eine PSP5-Zahl, denn mit 1541=23× 67 gilt: 522º 1 mod 23 (kleiner Fermat) Þ 51540=(522)70º 1 mod 23
    und entsprechend 51540=(566)23× 522º 123× 522º 1 mod 67
    also: 23ï 51540-1 Ù 67ï 51540-1 Þ 23× 67=1541ï 51540-1

    •

    AUFGABE 3.59 
      a) Zeige, dass 91, 1105 und 1541 PSP3-Zahlen sind.
      b) Zeige, dass 217 und 1729 PSP5-Zahlen sind.
      c) Zeige, dass 25, und 29341 PSP7-Zahlen sind.
      d) Zeige, dass 29341=13× 37× 61 PSPb-Zahl für b=2, 3, 5 und 7 ist.

    Bei all den hier zu bearbeitenden Aufgaben geht es um das Potenzieren von Zahlen mit großen Exponenten. Daher soll an dieser Stelle ein schneller Potenzieralgorithmus vorgestellt werden, der - das muss zur Einschränkung gesagt werden - unter Turbo-Pascal leider auch schnell mit dem Problem der Bereichsüberschreitung kämpft. (Ohnehin lassen sich die hier genannten Probleme nur befriedigend mit einem nach oben nahezu unbeschränktem Integertyp durchführen.)
    Die Idee ist schnell geschildert: Will man z.B. 229 berechnen, so kann man das auf diese Weise tun 229=21× 24× 28× 216. Dabei gehen die Faktoren durch Quadrieren auseinander hervor - es wird aber nicht jedes Quadrat benötigt. Damit man erkennt, welcher Faktor mit zum Produkt gehört, sehe man sich die Dualzahldarstellung von 29 an 29=111012. Also muß der Faktor genau dann berücksichtigt werden, wenn eine 1 in der Dualzahldarstellung steht. Dies erkennt man aber am leichtesten im folgenden Algorithmus:

    29=2× 14+1
    14=2× 7+0
    7=2× 3+1
    3=2× 1+1
    1=2× 0+1

    also: 29=2(2(2(2(2× 0+1)+1)+1)+0)+1, d.h. der jeweilige Rest bei Division durch 2 gibt an, ob der Faktor berücksichtigt wird oder nicht. Damit ergibt sich der folgende an die PASCAL-Notation angelehnte Algorithmus zur Berechnung von be:

    z:=1; x:=b;
    WIEDERHOLE
    WENN e MOD 2 =1 DANN z:=z× x;
    x:=x× x;
    e:=e DIV 2;
    BIS e=0;

    z enthält dann den Wert von be. Damit dieser bei den betrachteten Problemen nicht so schnell den LONGINT-Bereich überschreitet, werden tunlichst alle Multiplikationen modulo n ausgeführt. Hat man nun einen Exponenten von ca. 10000, so müssen statt einer Schleife mit 10000 Multiplikationen lediglich 14 Quadrierungen und maximal 14 Multiplikationen ausgeführt werden, was natürlich einen beträchtlichen Zeitgewinn bewirkt.

    Wir können dann an einer Wertebelegungstabelle die Bildung der Potenz verfolgen:

    z

    1

    2

    -

    2× 24

    25× 28

    213× 216

    x

    2

    22

    24

    28

    216

    232

    e

    29

    14

    7

    3

    1

    0

     

    AUFGABE 3.60
    Berechne per Hand 222, 333, 519 und 750 nach dem obigen Algorithmus. Schreibe dazu die Wertebelegungstabelle auf.

    Im Jahr 1912 entdeckte der Amerikaner Carmichael eine besondere Spezies von PSP-Zahlen. Diese Zahlen n teilen an-1-1 für alle aÎZ mit ggT(a,n)=1.

    DEFINITION 3.7 
    Eine zusammengesetzte Zahl n mit nï an-1-1 für alle aÎ Z mit ggT(a,n)=1 heißt "absolute PSP-Zahl" oder "Carmichael-Zahl."

            Bemerkung: Manchmal findet man auch nï an-a für alle aÎ Z.

    Beispiel: Wir zeigen, daß 561 eine absolute PSP-Zahl ist.
    Es ist 561=3× 11× 17 und 561-1= 560=2× 280=10× 56=16× 35
    a560-1=(a2)280-1º 1-1=0 mod 3
    a560-1=(a10)56-1º 1-1=0 mod 11
    a560-1=(a16)35-1º 1-1=0 mod 17

    AUFGABE 3.61 
            Zeige, dass 1105, 6601 und 41041 absolute PSP-Zahlen sind.

    AUFGABE 3.62 
    Verifiziere an den folgenden großen absoluten PSP-Zahlen:
    z=p1× p2× × × pr ist abs. PSP-Zahl Û pi-1ï n-1 für i=1,2...,r
    188.461; 101.101; 115.921; 126.217; 162.401=17× 41× 233

    Zur Frage nach der Häufigkeit der PSP-Zahlen und der absoluten PSP-Zahlen gaben Selfridge und Wagstaff 1980 die folgende Tabelle an:

    x

    103

    104

    105

    106

    107

    108

    109

    1010

    PSP-Zahlen<x

    3

    22

    78

    245

    750

    2057

    5597

    14887

    abs. PSP-Zahlen<x

    1

    7

    16

    43

    105

    255

    646

    1547

     

    FERMATTEST:

    Aus dem kleinen Fermat'schen Satz kann man einen einfachen Test konstruieren, der Auskunft darüber gibt, ob eine gegebene Zahl zusammengesetzt ist, ohne dass man einen Faktor angeben muss.

    Nennen wir eine Zahl b "F-Zeugen von n", wenn bn-1 inkongruent 1 mod n ist, so ist n sicher zerlegbar, wenn man einen F-Zeugen b von n mit 2£b£n-2 findet. Für die meisten Nichtprimzahlen ist schon 2 ein F-Zeuge. Lediglich die absoluten PSP-Zahlen machen Probleme, da sie verhältnismäßig wenige und noch dazu große F-Zeugen besitzen. (nach B.Kaup, Einfache Primtests, in: Elemente der Mathematik Nr.4,1993, Birkhäuser)

    Beispiel: Eine Primzahl p besitzt keine F-Zeugen kleiner als p, da ja nach dem kleinen Fermat gilt: pï bp-1-1 , d.h. bp-1º 1 mod p für alle zu p teilerfremden b.

    Wählt man eine zusammengesetzte Zahl, z.B.35=5×7, so ist meistens 2 F-Zeuge dieser Zahl, so auch hier: 234=24× 8+2º 18× 4=4¹ 1 mod 5, also gilt nicht 5ï 234-1 und deshalb auch nicht 35ï 234-1.

    Allerdings gibt es widerspenstige Nichtprimzahlen, denn für die absoluten PSP-Zahlen ist erst der kleinste Primteiler ein F-Zeuge, und der kann schon recht groß sein. So hat z.B. die absolute PSP-Zahl z=9.624.742.921=1171×2341×3511 den Faktor 1171 als kleinsten F-Zeugen. Für alle zu z teilerfremden Basen a gilt ja zïaz-1-1. Betrachtet man nun den Rechenaufwand, der notwendig ist, um über dieses Verfahren die "Nichtprimheit" von z zu beweisen, so muss man sich klar machen, dass hier über 1000 Zahlen in die z.te Potenz erhoben werden müssen, was in der Größenordnung von z ja nicht gerade ein Klacks ist.

    FAZIT: Der Fermattest ist für die meisten Zahlen ein relativ schnelles Verfahren, wenn sie denn zusammengesetzt sind. Bei absoluten PSP-Zahlen und bei Primzahlen kann das Verfahren jedoch sehr lange dauern. Man kann sich deshalb natürlich beim Testen auf wenige Basen b (sinnvollerweise zufällig zwischen 1 und z-1 gewählt) beschränken, doch dabei gehen einem leicht die absoluten PSP-Zahlen durch die Lappen.

    AUFGABE 3.63
    Zeige, daß 2 F-Zeuge von 225, jedoch nicht von 6601 ist. Zeige dann, daß 7 F-Zeuge von 6601 ist.

    Wir fassen noch einmal zusammen:

     

     

    RABINTEST:

    Ein effektiveres Testverfahren fanden Rabin und Miller 1976. Es liefert zwar nicht mit absoluter Sicherheit Primzahlen, denn es handelt sich um ein probabilistisches Verfahren, doch die Fehlerwahrscheinlichkeit ist äußerst gering.

    Auch dieses Verfahren beruht auf dem "kleinen Fermat". Danach gilt ja eine für alle Primzahlen p ap-1º 1 mod p für zu p teilerfremde Zahlen. Leider gilt ja die Umkehrung nicht, wie wir zuvor gesehen haben, denn die PSPb-Zahlen haben zumindest für eine spezielle Basis ebenfalls diese Eigenschaft. Das wäre ja kein Problem, denn man könnte ja verschiedene Basen durchprobieren und damit die Störenfriede aussondern, wenn da nicht noch die absoluten PSP-Zahlen wären, die man mit keiner Basis kleiner als der kleinste Primfaktor erwischen kann. Rabin dachte nun darüber nach, ob es nicht doch einen Unterschied zwischen den "echten" Primzahlen und den absoluten Pseudoprimzahlen im Zusammenhang mit dem kleinen Fermat gibt - und er fand ihn: in der unverdächtigen Regel (K9): a× bº 0 mod p (prim) Þ aº0 Ú bº0 mod p (Kapitel 3.1)
    Zunächst einige Vorüberlegungen: Es ist nach dem kleinen Fermat 27126º 1 mod 127. Es gilt aber schon 2742º 1 mod 127. Das bedeutet 2742-1=(2721-1)× (2721+1)º 0 mod 127. Wegen (K9) ist dann einer der Faktoren kongruent 0, also 2721º 1 oder 2721º -1 mod 127. Wir halten also fest: erhält man arº 1 mod p durch mehrfaches Quadrieren, so ist einer der Vorgänger von a in dieser Folge +1 oder -1. Genauer: startet man nicht mit +1 oder -1, so kann bei einem Primzahlmodul p durch Quadrieren nur dann eine Potenz ar mit arº 1 mod p entstehen, wenn einer der Vorgänger kongruent zu -1 ist.

    Dies ist bei Nichtprimzahlen anders. So ist z.B. 672º 1 mod 561, obwohl 67 inkongruent ± 1 mod 561 ist.

    Nun muss man sich für irgendeine zu testende Zahl z dem Term az-1 durch möglichst viel Quadrieren nähern, um zu erkennen, ob der ein Vorgänger der möglichen Kongruenz az-1º 1 kongruent zu -1 ist. Ein Beispiel mit einer Primzahl: Ist z.B. p=41, so gilt p-1=40=23× 5 und mit dem kleinen Fermat für jedes zu p teilerfremde a: .
    (Der Deutlichkeit halber - und da HTML hier noch nicht so viel bietet, der obige Ausdruch nochmal anders: a hoch (2 hoch 3) mal 5).
    Wegen a2rº 1 mod p Û arº 1 oder arº -1 für Primzahlen p (siehe K9) muss dann eine der Zahlen oder oder kongruent zu 1 oder -1 sein. Genauer muss entweder schon a5º ± 1 sein oder, wenn dies nicht der Fall ist, eine der Zahlen oder kongruent -1 sein, denn da die angegebenen Zahlen durch Quadrieren auseinander hervorgehen, muss einer der Vorgänger kongruent -1 sein. Tatsächlich ist z.B. für a=2  210º -1 mod 41 oder für a=3  320º -1 mod 41. Für Primzahlen ist dies also eine Selbstverständlichkeit. Es gibt aber auch (allerdings sehr wenige) Nichtprimzahlen, die diese Eigenschaft haben.

    Betrachten wir die absolute PSP-Zahl z=561. Wegen ggT(561,2)=1 gilt sicher 2560º 1 mod 561. Nun zerlegen wir 561-1=560 in der Form 560=24× 35 und konstruieren eine Folge wie oben:
    c0º 235º 263 mod 561 (mit POTMOD berechnet)
    c1º 22× 35=(c0)2=2632º 166 mod 561
    c2º =(c1)2=1662º 67 mod 561
    c3º =(c2)2=672º 1 mod 561

    Und da haben wir nun den "Casus Knacktus": Es ist (c2)2º 1 mod 561, also (c2-1)(c2+1)º 0 mod 561. Das hat nach (K9) für Primzahlmodule p zur Folge c2º 1 oder c2º -1. Es gilt aber c2º 67. Folgerung: Der Modul 561 ist nicht prim!

    AUFGABE 3.64
    Überprüfe die Folge ci wie im Beispiel für
    a) z=1105     b) z=6601         c) z=5001    d) z=5101    e) z=6973     
    f) z=52673    g) z= 188461     h) z=6209    i) z=2047

    Nun definieren wir allgemein:

    DEFINITION 3.8
    Eine ungerade Zahl z heißt starke Pseudoprimzahl zur Basis b (SPSPb-Zahl) mit 2£ b<z, wenn mit z-1=2t× m, m ungerade, gilt: c0:=bmº ± 1 mod z oder cr:= mod z für mindestens ein r mit 1£ r<t.

    Man beachte, dass für die cr gilt: cr+1= - die Bildung der ci ist also nur für i=0 aufwendig, bei allen anderen muss man nur quadrieren.

    AUFGABE 3.65
    Konstruiere die Folge ci mit b=2 für die folgenden Primzahlen:
      a) 1861    b) 1993     c) 4001   d) 4049   e) 9473
    und die Nichtprimzahlen  f) 5109   g) 3521

    Jede Primzahl ist mit dieser Definition und dem oben ausgeführten Bemerkungen eine starke Pseudoprimzahl. Es gibt jedoch auch Nichtprimzahlen, die der Definition genügen.

    Dabei geht man am einfachsten nach den Basen b vor. Für b=2 findet man als kleinste Zahl 2047=29× 83. Für diese gilt: 2047-1=2046=2 1023.
    Wir untersuchen also c0=21023=211×93=204893º 1 mod 2047 und haben somit mit der Basis 2 einen Misserfolg erlitten, denn obwohl 2047 nicht prim ist, ist es SPSP2-Zahl!
    Aber bereits mit der Basis b=3 erhalten wir c0=31023º 1565 mod 2047, was bereits ausreicht, um die Zahl eindeutig als Nichtprimzahl zu identifizieren, denn es folgt 32046=(31023)2º 15652º 1013, also ein Widerspruch zum kleinen Fermat (wenn denn 2047 prim sein sollte!). Die Zahl 2047 scheitert also bereits an der Basis b=3.
    Die kleinste Nichtprimzahl, die sowohl bezüglich der Basis 2 als auch der Basis 3 SPSPb-Zahl ist, ist a=1.373.653=829× 1657=22× 343.413 (für b=2 ergibt sich c1=22× 343413º -1 mod a; für b=3 ist schon c0º 1 mod a, für b=5 sind sowohl c0 als auch c1 nicht kongruent ± 1 mod a); die kleinste SPSPb-Zahl für b=2,3 und 5 ist 25.326.001=2251× 11251. Überhaupt gibt es nur 13 solcher Zahlen unter 25.000.000.000. Allerdings gibt es nur eine Zahl in diesem Bereich, die stark pseudoprim bez. b=2,3,5 und 7 ist, nämlich die Zahl 3.215.031.751=151× 751× 28351. Prüft man aber mit b=2,3,5,7 und 11, so findet man unter 25× 109 nur prime SPSPb-Zahlen.

    Testet man nun eine beliebige gegebene Zahl z darauf, ob sie SPSPb-Zahl ist, so kann es vorkommen, dass man für irgendein b herausfindet, dass z bezüglich dieser Basis nicht stark pseudoprim und daher auch gewiss nicht prim ist. Man nennt ein solches b einen R-Zeugen für die Zerlegbarkeit von b.

    DEFINITION 3.9
    b mit 2£ b£ z ist ein R-Zeuge (für die Zerlegbarkeit) von z, wenn mit z-1=2t× m gilt: c0:=bm ist inkongruent ± 1 mod z und cr:= (b hoch ((2 hoch r)mal m)) ist inkongruent -1 für alle r mit 1<r<t.

    Beispiel: Es sei z=89. Dann ist z-1=88=23× 11. Mit b=2 erhält man c0:=211º 1 mod 89. 2 ist also kein R-Zeuge von z (wie sollte es auch, denn z ist ja prim). Entsprechend findet man unter 89 keine andere Zahl als R-Zeugen von 89.
    Mit z=93 jedoch ergibt sich: 92=2 23 und damit c0=223º 8 mod 93 und c1=(c0)2=64 mod 93. Damit ist 2 ein R-Zeuge von 93 und 93 damit nicht prim (was man für kleinere Zahlen natürlich einfacher finden kann).

    AUFGABE 3.66 
      Zeige, daß 2 R-Zeuge von 6601 und 41041 ist.

    Hat man einen R-Zeugen gefunden, so kann man sicher sein, dass z zerlegbar ist. Wie ist es aber, wenn man nach etlichen Versuchen keinen R-Zeugen findet? Muss man, wie beim Fermattest, nun sehr viele Zahlen mit sehr großen Zahlen potenzieren? Man muss nicht, denn Rabin bewies, dass jede zerlegbare Zahl n mindestens 0,75× (n-1) R-Zeugen kleiner als n besitzt. Wählt man also zufällig k Zahlen b aus, und keines dieser b erweist sich als R-Zeuge, so kann man die Testzahl z mit einer Fehlerwahrscheinlichkeit von 0,25k zur Primzahl erklären (wie oben beschrieben, reicht für Zahlen unter 25× 109 bereits der Test mit den Basen 2,3,5,7 und 11).

    Rabin selbst untersuchte mit seinem Testverfahren, welches die größte Primzahl unter g=2400 (121 Stellen) ist. Dabei schieden die Zahlen g-1 bis g-591 alle mit b=2 aus. Bei g-593 fand sich unter 100 getesteten Basen kein R-Zeuge. Rabin erklärte deshalb g-593 mit der Fehlerwahrscheinlichkeit p<4-100<10-60 zur Primzahl. 1977 erbrachte Williams den "exakten" Beweis, dass g-593 tatsächlich eine Primzahl ist. Allerdings ist bei solchen "exakten" Beweisen die Fehlerwahrscheinlichkeit durch eventuelle Denk-, Programmier- oder Rechenfehler als wesentlich höher einzuschätzen.
    Kaup (siehe oben) gibt folgenden Vergleich an: Wenn seit 10 Milliarden Jahren (d.h. etwa seit dem Urknall) 10 Milliarden Mathematiker jede Sekunde 10 Milliarden mal den Rabin-Test mit k=100 anwenden, dann ist die Wahrscheinlichkeit, dass dabei wenigstens einmal eine zerlegbare Zahl fälschlicherweise als prim erklärt wird, kleiner als 10-20, also praktisch gleich Null.
    Der Rabin-Test ist ein relativ schnelles und einfach zu programmierendes Primzahlverfahren. Allerdings ist er nur ein propabilistischer Test. Die intensive Forschung auf diesem Gebiet (insbesondere gefördert durch das Pentagon) bringt es mit sich, daß neue Verfahren auf den Markt kommen (oder auch nicht, wenn sie der militäischen Geheimhaltung unterliegen), die schneller und besser(?) sind. Seit 1983 gibt es den APR-Test, benannt nach den amerikanischen Zahlentheoretikern Adleman, Pomeranc und Rumely, der in akzeptabler Zeit einen exakten Nachweis auch großer Primzahlen erbringt. Im Gegensatz zum Rabin-Test setzt er jedoch Resultate aus der Algebraischen Zahlentheorie und der Umgebung des Reziprozitätsgesetzes (siehe weiter unten) voraus.

    1987 meldeten Cohen und Lenstra einen neuen Test, mit dem 213 stellige Zahlen in höchstens zehn Minuten abgearbeitet werden können.


    Hier werde ich bald noch einige Delphi-Programme zum Download zur Verfügung stellen; nachdem ich mich jedoch einige Jahre nicht intensiv mit der Materie beschäftigt habe, schein es mir sinnvoll, diese noch jeweils mit einer Hilfe zu versehen - und das dauert eben.

     

    PROGRAMMIERÜBUNGEN

    Die folgenden Aufgaben sollen durch PASCAL-Programme gelöst werden. Diese sollten die UNIT ZT benutzen, die schon die Standardoperationen enthält. Zu manchen Aufgaben müssen keine eigenen Programme erstellt werden, sondern nur bestehende Programme abgeändert werden.

    1) Welche Zahlen n teilen 2n+1? Untersuche bis 100.000 und bestimme die PFZ dieser Zahlen. Vermutung?

    2) Suche alle nat. Zahl n<100.000 mit 2nº z mod n für z=5,7,9,11,13,15,....

    3) Zeige, daß für n=4.700.063497 gilt: 2nº 3 mod n. (Dies ist das kleinste n mit dieser Eigenschaft. Benutze dazu die UNIT LANGZAHL)

    4) Bestimme jeweils die kleinste ungerade Zahl n mit 2nº z für z=4,6,8,10,16,32

    5) Für welche Primzahlen p gibt es Vielfache n von p, so daß 22º 2k mod n für festes k. Mache Versuche für k=1,2,3.

    6) Rn:=11...11 heißt REPUNIT. Faßt man sie als Zahl des Dezimalsystems auf, so gilt
    Rn=(10n-1):(10-1). Welche davon sind Primzahlen, welche nicht. Finde die Primfaktorzerlegungen. Definiert man allgemeiner Ra,n=(an-1)/(a-1) so erhält man die Repunits des a-er Systems. Beispiele
    R3,4=(34-1)/(31) =40= 1× 33+1× 32+1× 31+1× 30=11113 oder
    R4,3=(43-1)/(4-1)=21=1× 42+1× 41+1× 40=1114. Untersuche, welche der Ra,n Primzahlen sind für a=3,4,5,11 und n so groß wie LONGINT es zuläßt.

    7) Berechne für zn=n4+(n+1)4 die Reste, die mod zn ergeben. Bestimme die Primfaktorzerlegungen der zn.

         DownloadDownload Kap_3_5 (23 KB)
    Inhaltsverzeichnis vorherige Seite zum Seitenanfang naechste Seite Kontakt


    Copyright © Michael Dorner, Januar 2002.
    Impressum · Datenschutz