Liczby pierwsze
0 likes567 views
Prezentacja przedstawia metod? badania pierwszo?ci liczb specjalnego typu
![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](https://image.slidesharecdn.com/liczbypierwsze-120830163918-phpapp01/85/Liczby-pierwsze-21-320.jpg)
Liczby pierwsze
- 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
- 11. 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
- 12. 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
- 14. 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
- 15. 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
- 16. 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
- 17. 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
- 18. 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
- 19. 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
- 23. 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
- 24. 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
- 25. 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