li:=[]:a:=2:
for p from 2 to 1000 do
if powermod(a,p-1,p)=1 and not isprime(p) then
li:=li.[p]:
end_if:
end_for:
["a=",a,"p=",li];
map(li,factor);
Pseudo-Primzahlen und Carmichael-Zahlen
Prof. Dr. Dörte Haftendorn, Mathematik mit MuPAD 4 Okt.08
http://haftendorn.uni-lueneburg.de www.mathematik-verstehen.de
####################################################################
Alle Zahlen, die a^(p-1)mod p=1 für mindestens ein a>1 erfüllen, heißen Pseudoprimzahlen.
Es sind also die Primzahl-Kandidaten, die der Kleine Fermat bei einmaliger Prüfung liefert.
1.) Es werden die Basen 2,3,...8 genommen und jedesmal eine Liste der
Pseudoprimzahlen bis 1000 erzeugt.
Die Primfaktorzerlegung dieser Pseudoprimzahlen wird angezeigt.
2.) Es wird die Carmichael-Zahl 561 untersucht.
#############################################################
Kleiner Fermat: Wenn p prim und ggt(a,p)=1, dann gilt: a^(p-1) mod p=1
li:=[]:a:=2:
for p from 2 to 1000 do
if powermod(a,p-1,p)=1 and not isprime(p) then
li:=li.[p]:
end_if:
end_for:
["a=",a,"p=",li];
map(li,factor);
Also sieht man hier 2^340 mod 341 =1 und 341 ist die kleinste Pseudoprimzahl
zur Basis 2.
li:=[]:a:=3:
for p from 2 to 1000 do
if powermod(a,p-1,p)=1 and not isprime(p) then
li:=li.[p]:
end_if:
end_for:
["a=",a,"p=",li];
map(li,factor);
Also sieht man hier 2^90 mod 91 =1 und 91 ist die kleinste Pseudoprimzahl
zur Basis 3.
li:=[]:a:=4:
for p from 2 to 1000 do
if powermod(a,p-1,p)=1 and not isprime(p) then
li:=li.[p]:
end_if:
end_for:
["a=",a,"p=",li];
map(li,factor);
Also sieht man hier 4^14 mod 15 =1 und 15 ist die kleinste Pseudoprimzahl
zur Basis4.
li:=[]:a:=5:
for p from 2 to 1000 do
if powermod(a,p-1,p)=1 and not isprime(p) then
li:=li.[p]:
end_if:
end_for:
["a=",a,"p=",li];
map(li,factor);
Also sieht man hier 5^3 mod 4 =1 und 4 ist die kleinste Pseudoprimzahl
zur Basis 5.
li:=[]:a:=6:
for p from 2 to 1000 do
if powermod(a,p-1,p)=1 and not isprime(p) then
li:=li.[p]:
end_if:
end_for:
["a=",a,"p=",li];
map(li,factor);
li:=[]:a:=7:
for p from 2 to 1000 do
if powermod(a,p-1,p)=1 and not isprime(p) then
li:=li.[p]:
end_if:
end_for:
["a=",a,"p=",li];
map(li,factor);
li:=[]:a:=8:
for p from 2 to 1000 do
if powermod(a,p-1,p)=1 and not isprime(p) then
li:=li.[p]:
end_if:
end_for:
["a=",a,"p=",li];
map(li,factor);
8^8, 8^8/9.0, powermod(8,8,9)
561 ist Carmichael-Zahl, das ist eine Zahl, die nicht Primzahl ist,
aber dennoch für alle a, die teilerfremd sind erfüllt: a^(p-1) mod p=1.
561 ist die kleinste Carmichael-Zahl.
li:=[]:p:=561:
factor(561);
for a from 2 to 35 do
if powermod(a,p-1,p)=1 then
li:=li.[a]:
end_if:
end_for:
["p=",p,"a=",li];
In dieser Liste fehlen also nur die Zahlen mit gcd(a,p)<>1, die also nicht teilerferemd zu 561 sind.
Dies zeigt auch die folgende Liste, die nämlich leer bleibt.
li:=[]:p:=561:
factor(561);
for a from 2 to 1000 do
if powermod(a,p-1,p)=1 and gcd(a,p)<>1 then
li:=li.[a]:
end_if:
end_for:
["p=",p,"a=",li];
