docKleiner Satz von Fermat Kleiner Satz von Fermat
download 
Denúncia Transcrição
Kleiner Satz von Fermat Kleiner Satz von Fermat
PRIMZAHLTESTS ARBEISTBLATT Jens Bernheiden Kleiner Satz von Fermat Beispiel: p = 7 a 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 Ist a∈ ∈N kein Vielfaches der Primzahl p, so ist ap – 1 ≡ 1 (mod p). a Vielfaches von 7? a6 nein nein 16 = 1 26 = 64 Rest von a6 bei Division durch 7 a7 – 1 ≡ 1 (mod 7) ? =0.7+1 =9.7+1 ja ja Der kleine Satz von Fermat gilt nicht für zusammengesetzte Zahlen p, selbst dann nicht, wenn man die Voraussetzung „a kein Vielfaches von p“ in „ggT(a, p) = 1“ ändert. Beispiel: p = 8 a 1 2 3 4 5 6 7 8 9 10 a Vielfaches von 8? ggT(a, 8) a7 Rest von a7 bei Division durch 8 nein 1 1 =0.8+1 a8 – 1 ≡ 1 (mod 8) ? Obwohl ggT(__, 8) = ____, ist _____________________ modulo _____. ja PRIMZAHLTESTS FOLIE Jens Bernheiden Kleiner Satz von Fermat Beispiel: p = 7 a a Vielfaches von 7? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 nein nein nein nein nein nein ja nein nein nein nein nein nein ja nein nein nein nein nein nein ja nein nein nein nein Ist a∈ ∈N kein Vielfaches der Primzahl p, so ist ap – 1 ≡ 1 (mod p). Rest von a6 bei Division durch 7 a6 16 = 1 26 = 64 36 = 729 46 = 4096 15625 46656 117649 262144 531441 1000000 1771561 2985984 4826809 7529536 11390625 16777216 24137569 34012224 47045881 64000000 85766121 113379904 148035889 191102976 244140625 =0.7+1 =9.7+1 = 104 . 7 + 1 = 585 . 7 + 1 = 2232 . 7 + 1 = 6665 . 7 + 1 = 16807 . 7 + 0 = 37449 . 7 + 1 = 57920 . 7 + 1 = 142857 . 7 + 1 = 253080 . 7 + 1 = 426569 . 7 + 1 = 689544 . 7 + 1 = 1075648 . 7 + 0 = 1627232 . 7 + 1 = 2396745 . 7 + 1 = 3448224 . 7 + 1 = 4858889 . 7 + 1 = 6720840 . 7 + 1 = 9142857 . 7 + 1 = 12252303 . 7 + 0 = 16197129 . 7 + 1 = 21147984 . 7 + 1 = 27300425 . 7 + 1 = 34877232 . 7 + 1 a7 – 1 ≡ 1 (mod 7) ? ja ja ja ja ja ja nein ja ja ja ja ja ja nein ja ja ja ja ja ja nein ja ja ja ja Der kleine Satz von Fermat gilt nicht für zusammengesetzte Zahlen p, selbst dann nicht, wenn man die Voraussetzung „a kein Vielfaches von p“ in „ggT(a, p) = 1“ ändert. Beispiel: p = 8 a a Vielfaches von 8? ggT(a, 8) a7 1 2 3 4 5 6 7 8 9 10 nein nein nein nein nein nein nein ja nein nein 1 2 1 4 1 2 1 8 1 2 1 128 2187 16384 78125 279936 823543 2097152 4782969 10000000 Rest von a7 bei Division durch 8 =0.8+1 = 16 . 8 + 0 = 273 . 8 + 3 = 2048 . 8 + 0 = 9765 . 8 + 5 = 34992 . 8 + 0 = 102942 . 8 + 7 = 262144 . 8 + 0 = 597871 . 8 + 1 = 1250000 . 8 + 0 a8 – 1 ≡ 1 (mod 8) ? ja nein nein nein nein nein nein nein ja nein Obwohl ggT(3, 8) = 1, ist 38 – 1 nicht kongruent zu 1 modulo 8.
