狠狠撸

1. Du?e ale nie za du?e liczby pierwsze. Sebastian Agata sierpie? 2012 Sebastian Agata () Du?e ale nie za du?e liczby pierwsze. sierpie? 2012 1 / 12

2. Jak szybko sprawdzi?, czy liczba 2k ?1 jest pierwsza? Sebastian Agata () Du?e ale nie za du?e liczby pierwsze. sierpie? 2012 2 / 12

3. Twierdzenie. Je±li p jest liczb? pierwsz? nieparzyst? to ka?dy dzielnik liczby 2p ?1 jest postaci 2kp +1 dla pewnego k ≥0 . A dzielniki pierwsze liczby 2p ? 1 B dzielniki dowolne liczby 2p ? 1 Sebastian Agata () Du?e ale nie za du?e liczby pierwsze. sierpie? 2012 3 / 12

4. Twierdzenie (Fermat - 1640 rok) Dla dowolnej liczby pierwszej p i dowolnego a nie podzielnego przez p zachodzi: a p ?1 ≡ 1 (mod p ) . Sebastian Agata () Du?e ale nie za du?e liczby pierwsze. sierpie? 2012 4 / 12

5. Lemat. (2a ? 1, 2b ? 1) = 2(a,b) ? 1 . dygresja na temat algorytmu Euklidesa Dla liczb ca?kowitych a b , przy czym b >0 istnieje dok?adnie jedna para liczb ca?kowitych , q r a = q · b + r, oraz 0 ≤ r < b. ?atwo zauwa?y?, ?e (a, b) = (b, r = a ? q · b) Sebastian Agata () Du?e ale nie za du?e liczby pierwsze. sierpie? 2012 5 / 12

6. Lemat. (2a ? 1, 2b ? 1) = 2(a,b) ? 1 . dygresja na temat algorytmu Euklidesa Dla liczb ca?kowitych a b , przy czym b >0 istnieje dok?adnie jedna para liczb ca?kowitych , q r a = q · b + r, oraz 0 ≤ r < b. ?atwo zauwa?y?, ?e (a, b) = (b, r = a ? q · b) Sebastian Agata () Du?e ale nie za du?e liczby pierwsze. sierpie? 2012 5 / 12

7. 20=6·3+2 3=1·2+1 2=2·1+0 (20, 3) = (3, 2 = 20 ? 6 · 3) = = (2, 1 = 3 ? 1 · 2) = (1, 0) = 1 Sebastian Agata () Du?e ale nie za du?e liczby pierwsze. sierpie? 2012 6 / 12

8. 20=6·3+2 3=1·2+1 2=2·1+0 (20, 3) = (3, 2 = 20 ? 6 · 3) = = (2, 1 = 3 ? 1 · 2) = (1, 0) = 1 Sebastian Agata () Du?e ale nie za du?e liczby pierwsze. sierpie? 2012 6 / 12

9. (2a ? 1, 2b ? 1) = (2a ? 1) ? (2b ? 1), 2b ? 1 = = (2a ? 2b , 2b ? 1) = (2b (2a?b ? 1), 2b ? 1) = (2a?b ? 1, 2b ? 1) = . . . = = (2(a,b) ? 1, 0) = 2(a,b) ? 1 Sebastian Agata () Du?e ale nie za du?e liczby pierwsze. sierpie? 2012 7 / 12

10. q | 2p ? 1 oraz q ∈P q | 2q?1 ? 1. (2p ? 1, 2q?1 ? 1) = 2(p,q?1) ? 1. q | 2p ? 1 q | 2 q ?1 ? 1 . q | 2(p,q?1) ? 1 Sebastian Agata () Du?e ale nie za du?e liczby pierwsze. sierpie? 2012 8 / 12

13. 2(p ,q ?1) ? 1 > 1 ? (p , q ? 1) > 1 ? (p , q ? 1) = p ? p | q ? 1 . q ? 1 = tp q = tp + 1 tp jest parzysta. t = 2k q = 2kp + 1 Sebastian Agata () Du?e ale nie za du?e liczby pierwsze. sierpie? 2012 9 / 12

20. Twierdzenie. Je±li p jest liczb? pierwsz? nieparzyst? to ka?dy dzielnik liczby 2p ?1 jest postaci 2kp +1 dla pewnego k ≥0 . A dzielniki pierwsze liczby 2p ? 1 B dzielniki dowolne liczby 2p ? 1 (2ap + 1)(2bp + 1) = 2(2abp + a + b)p + 1 Sebastian Agata () Du?e ale nie za du?e liczby pierwsze. sierpie? 2012 10 / 12

21. makelist ([k , 2k ? 1, primep (2k ? 1)], k , 1, 20); 10 1023 false 11 2047 false 12 4095 false 13 8191 true 14 16383 false 15 32767 false 16 65535 false 17 131071 true 18 262143 false 19 524287 true 20 1048575 false Sebastian Agata () Du?e ale nie za du?e liczby pierwsze. sierpie? 2012 11 / 12

22. Badamy czy rzeczywi±cie 219 ? 1 = 524287 ∈ P. Badamy dzielniki pierwsze liczby 219 ? 1 , które s? mniejsze od 724 poniewa? √ 524287 ≈ 724.077 Z ostatniego twierdzenia wiemy, ?e dzielniki liczby 219 ?1 s? postaci 2k · 19 + 1 = 38k + 1 . 39,77,115,153,191, 229,267,305,343,381, 419,457,495,533,571, 609,647,685,723,761 Sebastian Agata () Du?e ale nie za du?e liczby pierwsze. sierpie? 2012 12 / 12

狠狠撸

Liczby pierwsze

Recommended

More Related Content

Viewers also liked (15)

Liczby pierwsze