MM&AlK
Liczby doskonałe
Wspomniane w notce Tajemnica liczb (2) liczby Mersenne’a bardzo ściśle związane są z liczbami doskonałymi.
Na stronie 69 Wstępu do teorii liczb Wacława Sierpińskiego znajdziemy dowód twierdzenia mówiącego, że: Na to żeby liczba naturalna parzysta n była liczbą doskonałą, potrzeba i wystarcza, żeby była postaci 2s – 1(2s – 1), gdzie s i 2s – 1 są liczbami pierwszymi.
Wniosek wynikający z dowodu: Wszystkie liczby doskonałe parzyste są to liczby postaci
2p – 1(2p – 1), gdzie p i 2p – 1 są liczbami pierwszymi. Krótszy zapis: liczby doskonałe to liczby postaci 2p – 1Mp, gdzie Mp jest liczbą pierwszą Mersenne’a.
Liczby doskonałe nie są wymysłem współczesnych matematyków… Pitagorejczycy nazywali liczbę naturalną N liczbą doskonałą taką, której suma podzielników (bez liczby N) była równa tej liczbie. O takiej własności mówimy. Prostymi przykładami takich kolejnych liczb doskonałych są np. liczby:
6 = 1 + 2 + 3
28 = 1 + 2 + 4 + 7 + 14
496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248.
Te trzy liczby doskonałe znane były już w starożytności. Liczbami doskonałymi zajmował się już Euklides (III w p.n.e.) podając sposób ich znajdowania. Sposób Euklidesa polega na obliczaniu sum cząstkowych postępu geometrycznego. Jeżeli suma cząstkowa jest liczbą pierwszą, to po wymnożeniu jej przez ostatni składnik otrzymujemy liczbę doskonałą.
Liczby zaprzyjaźnione
Własnościami liczb naturalnych z pasją zajmowali się starożytni grecy a w szczególności pitagorejczycy. Analizując własności liczb pitagorejczycy zdefiniowali wspomniane liczby doskonałe, liczby zaprzyjaźnione i liczby wielokątne.
Z liczbami zaprzyjaźnionymi związana jest anegdota. Otóż, gdy spytano Pitagorasa: „Co to jest przyjaciel?” – Odpowiedział:
„Przyjaciel to drugi ja: przyjaźń to stosunek liczb 220 i 284”.
Jest to odpowiedź bardzo ciekawa bowiem liczby zaprzyjaźnione A, B, to liczby w których suma podzielników liczby A (bez liczby A) równa się liczbie B, i odwrotnie suma podzielników liczby B (bez liczby B) jest równa liczbie A. Jest więc:
A = 1 + 2 + 4 + 71 + 142.
Wszystkie kolejne składniki sumy są podzielnikami liczby 284.
B = 1 + 2 + 4 + 5 + 10 +11 + 20 + 22 + 44 + 55 + 110.
Wszystkie kolejne składniki sumy są podzielnikami liczby 220.
Liczbami zaprzyjaźnionymi zajmowali się Fermat, Kartezjusz, Euler. Obecnie znanych jest wiele par liczb zaprzyjaźnionych nieparzystych – gorzej z liczbami zaprzyjaźnionymi z których jedna byłaby liczbą parzystą a druga nieparzystą. W tym temacie praktycznie istnieje „pustynia”...
Liczby pierwsze
Liczby pierwsze, to liczby najbardziej tajemnicze i intrygujące z całego zbioru liczb naturalnych... Pojawiają się w najbardziej nieprzewidywalnych momentach. Liczby pierwsze definiujemy jako liczby, które dzielą się tylko przez liczbę jeden i przez samą siebie. Najciekawszym w liczbach pierwszych jest fakt, że liczby pierwsze kojarzone są z liczbami nieparzystymi, natomiast najmniejszą liczbą pierwszą jest liczba 2. W rzeczy samej, każda liczba naturalna większa od jedności jest iloczynem skończonej liczby liczb pierwszych.
Każda liczba złożona N ma dzielnik będący liczbą pierwszą mniejszą lub równą pierwiastkowi liczby N. Tak więc aby przekonać się, czy dana liczba N jest liczbą pierwszą, dzielimy tą liczbę przez liczby naturalne większe od jedności a mniejsze lub równe pierwiastkowi tej liczby. Jeżeli żadna z liczb nie jest podzielnikiem liczby N, to liczba jest liczba pierwszą. Liczba pierwsza dzieląca iloczyn skończonej liczby liczb naturalnych, jest dzielnikiem przynajmniej jednego z czynników tego iloczynu.
Sposoby wyznaczania liczb pierwszych
Już starożytni Grecy znali podstawowe własności liczb pierwszych. Zagadnienie liczb pierwszych i czynników pierwszych porusza Euklides w Elementach - podręczniku geometrii klasycznej. Starożytni Grecy wszelkie działania wykonywali nie na liczbach lecz na odcinkach. Odcinki można dodawać, odejmować, mnożyć, dzielić, potęgować i pierwiastkować...
Nie istnieją wzory na znajdowanie liczb pierwszych. Do chwili obecnej najefektywniejszą i wydajną metodą znajdowania i sporządzania obszernych wykazów liczb pierwszych jest Sito Eratostenesa z Cyreny – greckiego myśliciela i matematyka. Sito jest prostym sposobem (algorytmem) znajdowania wszystkich kolejnych liczb pierwszych. Liczby pierwsze znajdujemy poprzez skreślanie ich kolejnych wielokrotności. Zaczynamy od liczby 2. Liczbę 2 pozostawiamy, skreślamy natomiast kolejno 4,6,8... (kolejne liczby parzyste). Następnie pozostawiamy liczbę 3. Skreślamy wielokrotności tej liczby: 9, 15, 21, 27... Dalej postępujemy tak samo z kolejnymi liczbami... Pozostawione przez nas liczby są liczbami pierwszymi.
Współcześnie, wraz z rozwojem informatyki i szerokiego stosowania programów szyfrujących, niezastąpione są liczby pierwsze. Nad efektywnym sposobem znajdowania liczb pierwszych bez przerwy pracują zarówno matematycy jak i informatycy. Obecnie najbardziej popularnymi sposobami znajdowania liczb pierwszych jest Sito liniowe, czyli algorytm ACMs oraz Sito Atkina-Bernsteina. Sito liniowe, czyli algorytm ACMs opracowali informatycy: David Gries oraz Jayadev Misra. Sito Atkina-Bernsteina opracowali: matematyk Arthur Oliver Lonsdale oraz Daniel Julius Bernstein –matematyk, kryptolog i programista.
W algorytmach szyfrujących, do przekształcania przesyłanej informacji w tajny kod, niezbędne są bardzo duże liczby pierwsze. Poszukiwania bardzo dużych liczb pierwszych dla algorytmów szyfrujących np. dla algorytmu RSA, sprowadza się do poszukiwania dużych liczb Mersenne’a o wykładnikach będących liczbami pierwszymi. Liczba 2p w zapisie dwójkowym, to liczba jeden z ciągiem p zer. Liczba 2p – 1, to ciąg jedynek. Taki zapis cyfrowy pozwala badać bardzo duże liczby testem Lucasa-Lehmera (test pierwszości). Test pierwszości odpowiada na pytanie, czy dana liczba jest liczbą pierwszą. Szeroko stosowany jest również test pierwszości Milera-Rabina opracowany w 1975 roku ( o szyfrowaniu, dużych liczbach pierwszych i o zagrożeniach w odrębnej notce).
Pitagorejczycy twierdzili, że liczba jest modelem na podstawie której kształtują się rzeczy i każda rzecz ma swój model. W tym rozumieniu liczba jest czymś realnie istniejącym i stanowi wzorzec każdej rzeczy i całego świata… O tym w kolejnej notce.
