Liczby pierwsze i złożone
Na lekcji zapoznasz się z liczbami pierwszymi i złożonymi,
dowiesz się, jak sprawdzać, czy dana liczba jest pierwsza, jak
rozkładać liczbę na czynniki pierwsze, jak znajdować największy
wspólny dzielnik i najmniejszą wspólną wielokrotność.
Wpisz do okienka oznaczonego "a =
" dowolną liczbę naturalną, np. 53 i naciśnij "Sprawdź".
Otrzymałeś odpowiedź, że liczba 53 jest liczbą
pierwszą.
Wpisz teraz liczbę 2001.
Otrzymałeś liczbę 2001 w postaci iloczynu trzech liczb
pierwszych 3*23*29, więc jest to liczba złożona.
Zadanie 1.
Która z liczb: 23, 203, 2003, 20003, 200003, 2000003,
20000003, 200000003 jest liczbą pierwszą?
Zadanie 2.
Która z liczb postaci 2.10n-1,
gdzie n < 9, jest liczbą pierwszą?
A teraz samodzielnie sprawdź, czy wybrane przez Ciebie liczby
są pierwsze, czy złożone. Aby sprawdzanie nie było zbyt
monotonne, w każdym przykładzie, gdy liczba okaże się liczbą
pierwszą, zwróć uwagę na to, jaką cyfrą się ona kończy.
Liczba pierwsza musi kończyć się cyfrą 1 lub 3 lub 7
lub 9. Jedyny wyjątek to liczba 2, która jest liczbą
pierwszą, a kończy się cyfrą 2.
Zabaw się teraz w prostą zgadywankę.
"Duże" liczby pierwsze
Weź liczbę większą od 100 milionów, np. 100000007 i
zobacz, jak szybko program sprawdzi, czy jest to liczba pierwsza.
Po kilku sekundach program podaje odpowiedź, że jest to
liczba pierwsza.
Sprawdź inne "duże" liczby.
Okazuje się, że dla liczb nawet bliskich miliarda
program podaje odpowiedź po kilku sekundach. Największą
liczbą, jaką można wpisać do programu jest 999999999.
Czy domyślasz się, w jaki sposób program wykonuje
sprawdzenie i dlaczego robi to tak szybko?
Sposób jest dość prosty i okazuje się, że wcale nie
trzeba wykonywać tak dużo obliczeń. Dla liczby 100000007
program bierze kolejne liczby naturalne od 2 do 10000 i
sprawdza, czy któraś z nich dzieli 100000007. Jeśli żadna
jej nie dzieli, to jest to liczba pierwsza, w przeciwnym
przypadku jest to liczba złożona. Dlaczego wystarczy
sprawdzać podzielność tylko przez liczby do 10 tysięcy?
Gdyby liczba miała większy czynnik niż 10 tysięcy,
to miałaby również czynnik mniejszy od 10 tysięcy, a
ten zostałby wcześniej wykryty i liczba byłaby złożona.
A dwóch czynników większych od 10 tysięcy nie może
mieć, bo ich iloczyn przekroczyłby 100 milionów. Zatem
sprawdzanie należy prowadzić do pierwiastka z danej
liczby, w naszym przypadku do 
, czyli do 10 tysięcy.
Zadanie 3.
Ile dzieleń należy wykonać, aby stwierdzić, że liczba
2003 jest liczbą pierwszą?
Zadanie 4.
Napisz własny program sprawdzający, czy liczba 2000000003
jest liczbą pierwszą.
Zadanie 5.
Ile dzieleń należy wykonać, aby sprawdzić, że
trzydziestocyfrowa liczba 200000000000000000000000000003 jest
liczbą pierwszą? Jak długo będzie trwać sprawdzanie, jeśli
jedno dzielenie trwa 
sekundy?
Z powyższych rozważań wynika, że sprawdzanie, czy liczba
jest pierwsza, poprzez wykonywanie kolejnych dzieleń, nie jest
jednak takie szybkie.
Czy istnieje wzór dający same liczby pierwsze?
Sprawdź, czy ze wzoru 210n + 1 otrzymasz same liczby
pierwsze.
210 . 1 + 1 = 210 - liczba pierwsza;
210 . 2 + 1 = 421 - liczba pierwsza;
210 . 3 + 1 = 631 - liczba pierwsza;
210 . 4 + 1 = 841 = 29 . 29 - liczba złożona.
Zatem wzór 210n + 1 nie jest dobry.
Sprawdź, czy ze wzoru n2 + n +
17 (Adrien Legendre, XVIII w.) otrzymasz same liczby pierwsze.
12 + 1 + 17 = 19 - liczba pierwsza;
22 + 2 + 17 = 23 - liczba pierwsza;
32 + 3 + 17 = 29 - liczba pierwsza;
42 + 4 + 17 = 37 - liczba pierwsza;
52 + 5 + 17 = 47 - liczba pierwsza;
62 + 6 + 17 = 59 - liczba pierwsza;
72 + 7 + 17 = 73 - liczba pierwsza;
82 + 8 + 17 = 89 - liczba pierwsza;
92 + 9 + 17 = 107 - liczba pierwsza;
102 + 10 + 17 = 127 - liczba pierwsza;
112 + 11 + 17 = 149 - liczba pierwsza;
122 + 12 + 17 = 173 - liczba pierwsza;
132 + 13 + 17 = 199 - liczba pierwsza;
142 + 14 + 17 = 227 - liczba pierwsza;
152 + 15 + 17 = 257 - liczba pierwsza;
162 + 16 + 17 = 289 - liczba pierwsza;
172 + 17 + 17 = 323 = 17 . 19 - liczba
złożona. Zatem wzór n2 + n +
17 również nie jest dobry.
Sprawdź, czy ze wzoru n2 + n +
41 (Leonhard Euler, XVIII w.) otrzymasz same liczby pierwsze.
Oto 40 początkowych liczb otrzymanych z tego wzoru:
43, 47, 53, 61, 71, 83, 97, 113, 131, 151, 173, 197, 223, 251,
281, 313, 347, 383, 421, 461, 503, 547, 593, 641, 691, 743,
797, 853, 911, 971, 1033, 1097, 1163, 1231, 1301, 1373, 1447,
1523, 1601, 1681, ...
Sprawdzając 20 początkowych liczb tego ciągu, okazuje się,
że wszystkie są pierwsze. Dalsze wpisywanie liczb do
programu staje się męczące, ale gdy zauważymy, że dla n
= 41 otrzymujemy z tego wzoru 41.(41+1+1), to mamy
odpowiedź, że wzór n2 +n +
41 również nie daje samych liczb pierwszych.
Zadanie 6.
Sprawdź, czy ze wzoru 
(Pierre
Fermat, XVII w.) otrzymasz same liczby pierwsze.
Zadanie 7.
Sprawdź, czy ze wzoru 2p - 1, gdzie p
jest liczbą pierwszą (Marin Mersenne, XVII w.) otrzymasz
same liczby pierwsze.
Zadanie 8.
Z liczb pierwszych budujemy następujący ciąg:
2+1, 2.3+1, 2.3.5+1, 2.3.5.7+1,
2.3.5.7.11+1, 2.3.5.7.11.13+1,
2.3.5.7.11.13.17+1,
...
a) Czy prawdą jest, że żaden wyraz tego ciągu nie dzieli
się przez żadną liczbę pierwszą wchodzącą w skład
iloczynu występującego w danym wyrazie?
b) Sprawdź, czy wszystkie wyrazy tego ciągu są liczbami
pierwszymi.
Podsumowując rozważania tej części lekcji, należy
stwierdzić, że nie jest znany prosty wzór ani przepis
na liczby pierwsze.
Wyznaczanie liczb pierwszych za pomocą komputera
Mimo, że nie jest znany prosty wzór dający same liczby
pierwsze, programy komputerowe typu Derive, Mathematica, MuPAD,
itp. potrafią szybko i skutecznie wyznaczać liczby pierwsze.
Opis algorytmów stosowanych w tych programach wykracza poza ramy
tego opracowania, prześledźmy więc jedynie efekt ich działania.
Funkcja NEXT_PRIME (następna pierwsza), jaką
posiadają te programy, daje następujące wyniki:
NEXT_PRIME(100) = 101
NEXT_PRIME(10000000000) = 10000000019
NEXT_PRIME(314159265358979) = 314159265359057
NEXT_PRIME(1050) =
10000000000000000000000000000000000000000000000151
NEXT_PRIME(10100) =
100000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000267
Zadanie 9.
Jeśli masz dostęp do jednego ze wspomnianych wyżej programów
komputerowych, wyznacz liczbę pierwszą większą od 10500.
Zmierz czas obliczeń.
Rozkład na czynniki pierwsze
Wpisz do programu, w okienko oznaczone symbolem "a
= ", liczbę 693 i naciśnij "Rozłóż".
Otrzymałeś rozkład tej liczby na czynniki pierwsze. Czy
widzisz, jaki sposób zastosowano do rozkładu?
Zasada rozkładu liczb na czynniki pierwsze
jest następująca:
należy brać kolejne liczby pierwsze i jeśli przez którąś
z nich liczba się dzieli, zapisać ten dzielnik i po
wykonaniu odpowiedniego dzielenia, kontynuować proces
dla otrzymanego ilorazu.
Rozłóż teraz wiele innych liczb na czynniki. Po wpisaniu
liczby do programu, a przed naciśnięciem "Rozłóż",
spróbuj zgadnąć, jaki będzie największy czynnik danej liczby.
Zadanie 10.
Jaki największy czynnik pierwszy może mieć liczba złożona
x?
Zadanie 11.
Czy liczba złożona x, może mieć dwa czynniki
pierwsze większe niż:
a) 
x; b) 
x; c) 
x ?
Zadanie 12.
Sprawdź, jaki rozkład na czynniki pierwsze mają ważne
daty Twojego życia, numery telefonów, numery rejestracyjne,
kody, piny, itp. Jeśli któryś jest ciekawy, możesz go
zapamiętać.
Zadanie 13.
Co zauważasz w rozkładzie podanej niżej liczby na czynniki
pierwsze?
a) 9699690; b) 3628800.
Rozkład "dużych" liczb na czynniki
pierwsze
Podczas rozważań o liczbach pierwszych stwierdziliśmy, że
sprawdzanie, czy liczba jest pierwsza, poprzez wykonywanie
kolejnych dzieleń, nie jest szybkie. Ponieważ rozkład na
czynniki polega również na kolejnym sprawdzaniu podzielności,
więc również będzie trwał długo. Sprawdź to na przykładzie
liczby 995061821.
Rozkład trwa kilka sekund i otrzymujemy odpowiedź
995061821 = 13 . 76543217.
W specjalistycznych programach rozkład liczb na czynniki trwa
dużo krócej, ale i tam, dla coraz większych liczb czas obliczeń
jest coraz dłuższy. Powstaje więc pytanie: czy istnieje jakiś
szybki sposób rozkładu liczby na czynniki, który nawet dla dużych
liczb, będzie trwał krótko? Zanim odpowiemy na to pytanie należy
uświadomić sobie, w czym tkwi problem. Np. aby obliczyć sumę
1+3+5+ ...+999999999, można za pomocą komputera dodawać
kolejne składniki, co trwałoby jednak dość długo. Możemy
jednak w ułamku sekundy wyznaczyć tę sumę ze wzoru n2
i otrzymujemy 5000000002 (przypomnij sobie lekcję o
ciągach). W tym właśnie jest problem: czy można rozłożyć
dużą liczbę na czynniki, nie sprawdzając podzielności przez
kolejne liczby?
Odpowiedź na to pytanie jest niestety negatywna. Nie
ma szybkiego sposobu rozkładu liczby na czynniki pierwsze.
Jeśli więc ktoś utworzy iloczyn dwóch dużych liczb
pierwszych i poda tylko ten iloczyn, to nikt nie potrafi
szybko wyznaczyć jego czynników.
Zadanie 14.
Liczba 121932631239183787279368837709 jest iloczynem dwóch
piętnastocyfrowych liczb pierwszych. Jeśli masz dostęp do
jednego ze wspomnianych wyżej programów komputerowych, rozłóż
ją na czynniki.
Paradoksalnie, trudność w rozkładzie dużych liczb na
czynniki pierwsze, stała się zbawienna w ważnym obszarze
zastosowań informatyki. Ponieważ łatwo i szybko można tworzyć
iloczyny dużych liczb pierwszych, a bardzo trudne, a właściwie
niemożliwe w realnym czasie, jest rozłożenie dużej liczby na
czynniki, stało się to podstawą najlepszych obecnie metod
szyfrowania danych. Możesz się z tym szczegółowo zapoznać w
lekcji "Zastosowanie liczb pierwszych - szyfrowanie
RSA".
NWD - Największy Wspólny Dzielnik
Zapoznasz się teraz ze sposobem wyznaczania największego wspólnego
dzielnika. Jest to bardzo ważne zagadnienie, ponieważ wszędzie
tam, gdzie występują jakiekolwiek obliczenia, prawie zawsze
trzeba upraszczać otrzymywane ułamki lub proporcje, zmieniać
skale, porównywać wielkości, itp.
Spróbuj uprościć ułamek 
, ale nie używaj jeszcze przycisku NWD.
Ponieważ 168 = 2.2.2.3.7,
zaś 105 = 3.5.7, więc widać, że
największą liczbą, przez którą należy skrócić ten ułamek
jest 3.7 = 21. Po skróceniu otrzymujemy 
= 1,6.
Z powyższego przykładu wynika, że wyznaczanie największego
wspólnego dzielnika dla małych liczb nie jest trudne: wystarczy
rozłożyć obie liczby na czynniki pierwsze i wziąć iloczyn
wspólnych czynników.
Wpisz do programu liczby a = 168 i b = 105 i
naciśnij "NWD".
Otrzymałeś 4 linijki prostych obliczeń i w piątej
odpowiedź: NWD(168,105) = 21. Jest to algorytm Euklidesa
wyznaczania największego wspólnego dzielnika. Stosuje się
go powszechnie w programach komputerowych i nie sposób nie
zauważyć, że to już drugi przypadek w dziedzinie liczb
pierwszych, gdzie odkrycie dokonane w starożytności ma
istotne zastosowanie we współczesnych technikach
komputerowych (pierwszy to sito Eratostenesa).
Spróbuj odkryć zasadę tego algorytmu. Zwróć uwagę na
to, że nigdzie nie ma dzielników 2, 2, 2, 3, 7 liczby 168,
ani dzielników 3, 5, 7 liczby 105, więc chyba nie trzeba
rozkładać liczb na czynniki.
Zasada wyznaczania NWD za pomocą algorytmu
Euklidesa jest następująca.
Mając dwie liczby, np. 168 i 105, wykonujemy dzielenie z
resztą: 168:105 = 1 reszta 63. Dla zobrazowania tego
dzielenia budujemy zapis: 168 = 1*105+63.
Następnie wykonujemy dzielenie z resztą liczby 105 i
reszty 63: 105:63 = 1 reszta 42; odpowiedni zapis: 105 =
1*63+42.
Następny krok wykonujemy analogicznie: 63:42 = 1 reszta
21; odpowiedni zapis: 63 = 1*42+21.
W kolejnym kroku otrzymujemy: 42:21 = 2 reszta 0; zapis:
42 = 2*21+0.
Ponieważ otrzymaliśmy resztę 0, proces jest zakończony,
a największym wspólnym dzielnikiem jest przedostatnia
reszta równa 21.
Zadanie 15.
Wyznacz dwoma sposobami (przez rozkład na czynniki i
algorytmem Euklidesa) największy wspólny dzielnik liczb:
a) 216 i 78; b) 1260 i 555; c) 5577 i 2730; d) 660807727
i 101490007.
Zadanie 16.
Wyznacz 20 początkowych wyrazów ciągu Fibonacciego i
sprawdź, które jego wyrazy są liczbami pierwszymi i które
dwa sąsiednie wyrazy są liczbami względnie pierwszymi.
Projekt
Opracuj cztery programy komputerowe wyznaczające największy
wspólny dzielnik czterema różnymi sposobami: przez rozkład na
czynniki, algorytmem Euklidesa z dzieleniem, algorytmem Euklidesa
z odejmowaniem, sposobem "naiwnym" (sprawdzanie
kolejnych liczb). Porównaj czas realizacji, długość ich kodu,
wielkość potrzebnej pamięci i złożoność obliczeniową każdego
programu i sformułuj odpowiednie wnioski.
NWW - Najmniejsza Wspólna Wielokrotność
Często chcemy dla dwóch danych liczb wyznaczyć liczbę, która
jest ich wspólną wielokrotnością. Oczywiście wystarczy je
pomnożyć, ponieważ iloczyn spełnia tę własność, ale
chcemy, żeby to była jak najmniejsza liczba. Np. dla liczb 70 i
42 taką liczbą jest 210, zawiera ona 3 siedemdziesiątki i 5
czterdziestekdwójek, zaś iloczyn jest dużo większy i wynosi aż
2940.
Wpisz do programu a = 70 i b = 42 i naciśnij
"NWW".
Otrzymałeś 3 linijki prostych obliczeń i odpowiedź 210.
Czy dostrzegasz sposób, w jaki zostało to obliczone?
Zasada obliczania NWW jest następująca:
Iloczyn liczb dzielimy przez największy wspólny
dzielnik tych liczb. Czy rozumiesz, dlaczego taki jest wzór?
Wyznaczając NWW, szukamy takiej liczby, która będzie
zawierać obie dane liczby. W iloczynie występują
obie liczby i każda zawiera NWD, zatem powtarza się
on dwukrotnie. Możemy więc podzielić przez niego i
będziemy mieli mniejszą liczbę zawierająca obie
liczby. Na przykład: NWD(70,
42)=14. Gdyby nie było dzielenia przez NWD, mielibyśmy
iloczyn 70 * 42. Ale 14 jest czynnikiem zarówno
liczby 70, jak i liczby 42, stąd 70*42 = 5*14*3*14.
Niepotrzebnie więc dwukrotne mnożyliśmy przez 14,
należy zatem przez 14 podzielić.
Zadanie 17.
Wyznacz NWW liczb:
a) 216 i 78; b) 1260 i 555; c) 5577 i 2730; d) 660807727 i
101490007.
Zadanie 18.
Wyznacz 20 początkowych wyrazów ciągu Fibonacciego i
sprawdź, dla której pary sąsiednich wyrazów NWW jest
mniejsza niż ich iloczyn.
Czy
istnieją inne sposoby wyznaczania NWW?
Ponieważ
NWW ma związek z NWD, więc może tak jak NWD, NWW również
da się wyznaczyć z rozkładu na czynniki pierwsze.
Tak jest
rzeczywiście. Spróbuj to zrobić samodzielnie.
Rozkładamy
obie liczby na czynniki pierwsze i w jednym z rozkładów
skreślamy te czynniki, które występują w drugim rozkładzie.
Iloczyn wszystkich pozostałych czynników z obu rozkładów
daje NWW.
Zadanie 19.
Wyznacz powyższym sposobem NWW podanych liczb:
a) 216 i 78; b) 1260 i 555; c) 5577 i 2730; d) 660807727 i
101490007.
Projekt
Opracuj programy komputerowe wyznaczające najmniejszą wspólną
wielokrotność różnymi sposobami. Porównaj czas realizacji, długość
ich kodu, wielkość potrzebnej pamięci i złożoność
obliczeniową każdego programu oraz sformułuj odpowiednie
wnioski.
Odpowiedzi
1. 23, 2003, 200003, 2000003, 20000003.
2. 19, 199, 1999, 199999, 19999999.
3. 44, ponieważ 
44.
4. Oto taki program, który działa dla liczb do 2147483647:
program Liczba_pierwsza_czy_zlozona;
uses crt;
var liczba,n:longint;
begin
clrScr;
liczba:=2000000003;
for n:=2 to round(sqrt(liczba)) do
if liczba mod n=0 then
begin
writeLn(liczba,'-liczba zlozona, dzielnik ',n);
readLn; exit;
end;
writeLn(liczba,'-liczba pierwsza');
readLn;
end.
Po uruchomieniu tego programu otrzymujemy po sekundzie
odpowiedź, że jest to liczba złożona i jej dzielnikiem
jest 17.
5. Pierwiastek kwadratowy z liczby trzydziestocyfrowej jest
liczbą około piętnastocyfrową, zatem należy wykonać około
1015 dzieleń. Jedno dzielenie trwa sekundy, stąd 1015 .
1012 sekund 1,6 . 1010 minut 277777778 godzin 11574074 dni 31000 lat.
6. Oto 4 początkowe liczby Fermata:
= 5 - liczba pierwsza;
= 17 - liczba pierwsza;
= 257 - liczba pierwsza;
= 65537 - liczba pierwsza.
Piąta liczba Fermata 
=
4294967297 jest już za duża, aby sprawdzić ją za pomocą
naszych programów. Ale bardziej zaawansowane programy, np.
Derive, podają, że jest to liczba złożona i jej dzielnikiem
jest 641. Sprawdź to dzielenie na kalkulatorze systemowym
Windows lub MacOS! Zatem wzór również
nie daje samych liczb pierwszych.
7. Oto 5 początkowych liczb Mersenne'a:
22 - 1 = 3 - liczba pierwsza;
23 - 1 = 7 - liczba pierwsza;
25 - 1 = 31 - liczba pierwsza;
27 - 1 = 127 - liczba pierwsza;
211 - 1 = 2047 = 23 . 89 - liczba złożona.
Zatem wzór 2p - 1, gdzie p jest pierwsze,
również nie daje samych liczb pierwszych. Jednak w tym
przypadku sytuacja jest dużo lepsza niż dla wszystkich
poprzednich wzorów. Okazało się, że istnieje prosty sposób
na sprawdzenie, czy liczba Mersenne'a jest liczbą pierwszą. Omówiono
to na lekcji "Liczby Mersenne'a - Test Lucasa".
8. a) Jest to prawda, ponieważ jeśli do iloczynu dowolnych
liczb (nie tylko pierwszych) dodamy jedynkę, to dzieląc tę sumę
przez którąś z tych liczb, otrzymamy resztę 1.
b) 2+1 = 3 - liczba pierwsza;
2.3+1 = 7 - liczba pierwsza;
2.3.5+1 = 31 - liczba pierwsza;
2.3.5.7+1 = 211 - liczba
pierwsza;
2.3.5.7.11+1 =
2311 - liczba pierwsza;
2.3.5.7.11.13+1
= 30031 = 59 . 509 - liczba złożona. Zatem nie jest
to przepis na liczby pierwsze.
9. Za pomocą programu Derive otrzymujemy:
NEXT_PRRIME(10500) =
100000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000961
Czas obliczeń na komputerze z procesorem 1000MHz: 15 sekund.
10. x, np. 34 = 17 .
2.
11. a) Nie; b) nie; c) tak, np. x = 6 = 2 .
3.
13. a) Jest to iloczyn liczb pierwszych mniejszych od 20; b)
jest to 2.3.4.5.6.7.8.9.10
= 10!
14. 121932631239183787279368837709 = 123456789098807 .
987654321234587 - czas obliczeń około 1 godziny.
15. a) 6; b) 15; c) 39; d) 2003;
16. Początkowe liczby pierwsze w ciągu Fibonacciego: 2, 3, 5,
13, 89, 233, 1597. Wszystkie pary sąsiednich wyrazów ciągu
Fibbonacciego są względnie pierwsze, ich NWD wynosi 1.
17. a) 2808; b)
46620; c) 390390; d) 33482466719363.
18. Wszystkie sąsiednie
wyrazy są względnie pierwsze, więc dla żadnej pary NWW nie
jest mniejsza od iloczynu.
19. a) 2808; b)
46620; c) 390390; d) 33482466719363.