MM&AlK
Liczby, w szczególności liczby pierwsze, mają niebagatelne znaczenie przy współczesnych technologiach cyfrowych… Duże liczby, dzielniki liczb, to domena wszelkich systemów szyfrowania… Słynny algorytm szyfrowania RSA oparty jest na wykorzystaniu właśnie dużych stu i więcej cyfrowych liczb pierwszych. O tym w kolejnych notkach… Na początek…
Kilka zdań o liczbach nieparzystych i ich własnościach
W teorii liczb, głównie badania własności liczb dla celów informatyki ukierunkowane są przede wszystkim na liczby pierwsze ale liczby pierwsze to liczby nieparzyste… Zaczniemy zatem od liczb nieparzystych.
Najczęściej liczby nieparzyste zapisujemy w postaci 2t + 1, gdzie liczba t jest liczbą parzystą lub nieparzystą. Dla liczb nieparzystych zachodzi zależność:
(2t + 1)n = 2T + 1
gdzie:
T jest liczbą parzystą, gdy t jest liczbą parzystą,
T jest liczbą nieparzystą, gdy t jest liczbą nieparzystą.
Jest bowiem: (2t + 1)n = 2{[(2t + 1)n – 1]/2} + 1 = 2T + 1
Liczby postaci 4k + 1 i 4k + 3
Jeśli dokładniej przyjrzymy się liczbom nieparzystym zauważymy, że zbiór liczb nieparzystych jest sumą dwóch podzbiorów... – Podzbioru Z = 4k + 3 i podzbioru X = 4k + 1, gdzie k = 0,1, 2, 3,…
Z uwagi na zależność Z = 4k + 3 = 4(k + 1) – 1 = 4K – 1, wygodniej jest przyjąć w analizach Z = 4k – 1
W podręcznikach i monografiach odnoszących się do teorii liczb, znajdziemy twierdzenia mówiące, że liczb pierwszych postaci
4k + 1 oraz postaci 4k + 3 (k = 1, 2, 3...) jest nieskończenie wiele.
Dla liczb postaci 4k + 1 znane jest twierdzenie Fermata mówiące, że Każda liczba pierwsza postaci 4k + 1 jest sumą dwóch kwadratów.
Natomiast dla liczb postaci 4k + 3 słusznym jest twierdzenie mówiące, że: Każda liczba naturalna postaci 4k + 3 ma przynajmniej jeden dzielnik będący liczbą pierwszą tej samej postaci.
Co nieco dodamy…
Matematyk Richard Mason pierwszy zauważył, że rozpatrując wykładniki n ≥ 2 równania Fermata, przeoczono pierwszą potęgę, czyli równanie: x1 + y1 = z1. Równanie wydaję się, mówiąc oględnie, banalne... Każdą z trzech zmiennych wyrażamy przecież za pomocą dwóch pozostałych. Jeśli wprowadzimy warunki pitagorejskie mówiące, że liczby x, y są liczbami względnie pierwszymi (x, y) = 1 i żadna z liczb nie jest potęgą liczby naturalnej oraz jedna z liczb x, y jest liczbą parzystą a druga liczbą nieparzystą wówczas równanie nabiera zupełnie innego kontekstu. Uwaga Masona stała się przyczynkiem do powstania tak zwanej, hipotezy ABC. Nie będziemy wnikać w zawiłości tej hipotezy… Zaczniemy od jej setna… Wyznaczmy liczby x, y, z spełniające równanie Fermata, a więc takie liczby, z których żadna z liczb nie jest potęgą liczby naturalnej, czyli wszystkie są potęgi pierwszej. Przyjmiemy zwyczajowo, że liczba x jest liczbą nieparzystą, natomiast liczba y liczbą parzystą. Równanie Fermata dla pierwszej potęgi:
x1 + y1 = z1
przekształcamy do postaci: z1 – x1 = y1
Liczby x, z są liczbami nieparzystymi. Przyjmiemy, że obie liczby nie są potęgami liczb naturalnych, z których jedna jest liczbą postaci np.
z = 4k + 1 a druga postaci x = 4t – 1,
wówczas różnica liczb wyniesie:
(4k + 1) – (4t – 1) = 4(k – t) + 2 = 2[2(k – t) + 1]
Zmieniając odpowiednio znaki otrzymujemy:
(4k – 1) – (4t + 1) = 4(k – t) – 2 = 2[2(k – t) – 1]
Liczba w nawiasie kwadratowym, prawej strony równania, jest liczbą nieparzystą, natomiast liczba 2 nie jest potęgą liczby naturalnej. Tak więc różnica liczb nieparzystych o takiej strukturze nie jest potęgą liczby naturalnej.
Istnieje zatem równanie x1 + y1 = z1 mające rozwiązanie w liczbach naturalnych, przy którym liczby x, y, z nie są potęgami liczb naturalnych.
Jest sprawą oczywistą, że różnica nieparzystych potęg tych liczb nieparzystych, także nie będzie potęgą liczby naturalnej.
Dowód wynika z tożsamości. Jest bowiem:
(4k + 1)n – (4t – 1)n = (4K + 1) – (4T – 1) = 2[2(K – T) + 1]
(4k – 1)n – (4t + 1)n = (4K – 1) – (4T + 1) = 2[2(K – T) – 1]
C.b.d.o.
Co jeszcze dodać…
W roku 1823 Abel sformułował twierdzenie (znane jako hipoteza Abela) mówiące, że jeżeli liczby całkowite, względnie pierwsze
x, y, z, gdzie 0 < x < y < z spełniają równanie Fermata
xn + yn = zn
dla n >2, to żadna z liczb x, y, z nie jest potęgą liczby pierwszej. Tak więc odwróciliśmy hipotezę Abela. Udowodniliśmy, że równanie Fermata jest prawdziwe (nie ma rozwiązań w liczbach naturalnych), dla nieparzystych potęg liczb pierwszych będących liczbami, jedna postaci (4k + 1)n, druga postaci (4t – 1)n. I tak wracamy do Pierre Fermata i jego twierdzenia…
Z innym twierdzeniem Pierre Fermata związane są liczby Mersenne’a, są to liczby postaci:
Mn = 2m – 1, gdzie m jest liczbą naturalną.
Liczby o dużych wykładnikach m, będącymi liczbami pierwszymi, są obowiązujące w szyfrowaniu… Im większe liczby stosujemy w szyfrowaniu, tym trudniej złamać szyfr… Czasami znalezienie dzielników wielkich liczb wydaje się niemożliwe… a jest banalnie proste…
Przykład: Znaleźć dzielniki liczby Mn = 2513 479 823 701 503 874 053 127 872 737 – 1.
Jakie są dzielniki tej liczby i jak to udowodnić?
