Jak Rozłożyć Liczbę na Czynniki Pierwsze
Rozkład na czynniki pierwsze to zapisanie liczby jako iloczynu samych liczb pierwszych, na przykład 360 = 2^3 × 3^2 × 5. Potrzebujesz go, żeby skrócić ułamek do najprostszej postaci, wypisać wszystkie dzielniki liczby, policzyć NWD lub NWW dwóch wartości, a w informatyce ten sam mechanizm stoi za bezpieczeństwem szyfrowania RSA. Poniżej pokazuję dokładnie, jak zrobić to ręcznie, metodą dzielenia próbnego, na dwóch konkretnych liczbach.
Ręczne dzielenie próbne
Zasada jest prosta: dzielisz liczbę przez najmniejszą możliwą liczbę pierwszą, dopóki się dzieli bez reszty, a gdy przestaje się dzielić, przechodzisz do kolejnej liczby pierwszej. Kończysz, gdy iloraz osiągnie 1.
Rozłóżmy 360. Zaczynamy od 2, bo to najmniejsza liczba pierwsza, a 360 jest parzyste:
| Krok | Dzielimy | Przez | Wynik |
|---|---|---|---|
| 1 | 360 | 2 | 180 |
| 2 | 180 | 2 | 90 |
| 3 | 90 | 2 | 45 |
| 4 | 45 | 3 | 15 |
| 5 | 15 | 3 | 5 |
| 6 | 5 | 5 | 1 |
Przy 45 dzielenie przez 2 przestaje działać (45 jest nieparzyste), więc przechodzimy do następnej liczby pierwszej, czyli 3, i dzielimy dwa razy z rzędu, aż zostaje 5. Piątka nie dzieli się już przez 3, więc próbujemy kolejnej liczby pierwszej, czyli samej 5, i wynik spada do 1. Koniec.
Czynniki użyte po drodze to 2, 2, 2, 3, 3, 5. Grupując powtórzenia w wykładniki, dostajemy 360 = 2^3 × 3^2 × 5. Warto sprawdzić wynik mnożeniem w drugą stronę: 2^3 = 8, 3^2 = 9, a 8 × 9 × 5 = 360. Zgadza się.
Większy przykład i test pierwszości
Weźmy teraz 1001, liczbę, przy której dzielenie przez 2, 3 i 5 od razu zawodzi (jest nieparzysta, cyfry sumują się do 2, nie kończy się na 0 ani 5). Próbujemy kolejno wyższe liczby pierwsze:
1001 ÷ 7 = 143 143 ÷ 11 = 13 13 ÷ 13 = 1
Więc 1001 = 7 × 11 × 13, trzy różne liczby pierwsze, każda w pierwszej potędze. Sprawdzenie: 7 × 11 = 77, a 77 × 13 = 1001.
Ten sam mechanizm dzielenia próbnego odpowiada na pytanie “czy ta liczba jest pierwsza?”, tylko że wtedy szukasz choćby jednego dzielnika i, jeśli go nie znajdziesz, liczba jest pierwsza. Sprawdźmy 997. Pierwiastek kwadratowy z 997 wynosi w przybliżeniu 31,6, więc wystarczy przetestować liczby pierwsze do 31 włącznie: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31. Żadna z nich nie dzieli 997 bez reszty (na przykład 31 × 32 = 992, zostaje reszta 5, a 29 × 34 = 986, zostaje reszta 11). Skoro żaden dzielnik pierwszy do pierwiastka kwadratowego nie pasuje, 997 jest liczbą pierwszą.
Kilka dodatkowych przykładów dla porównania:
| Liczba | Rozkład | Pierwsza czy złożona |
|---|---|---|
| 51 | 3 × 17 | złożona |
| 97 | 97 | pierwsza |
| 100 | 2^2 × 5^2 | złożona |
| 221 | 13 × 17 | złożona |
| 997 | 997 | pierwsza |
Zwróć uwagę na 221: na pierwszy rzut oka wygląda podejrzanie jak liczba pierwsza (nie kończy się na parzystej cyfrze, nie dzieli się łatwo przez 3 czy 5), ale 13 × 17 = 221, więc jest złożona. To dobry przykład na to, że “wyglądanie na pierwszą” nic nie znaczy, liczy się tylko faktyczne dzielenie próbne.
Oblicz z własnymi liczbami
Zamiast liczyć to ręcznie za każdym razem, wpisz dowolną liczbę całkowitą poniżej i zobacz od razu rozkład w postaci z wykładnikami, informację czy liczba jest pierwsza, oraz pełną listę dzielników.
Dowolna liczba całkowita do 1 000 000 000 000. Znak jest pomijany.
Wpisz liczbę całkowitą, aby zobaczyć jej rozkład na czynniki pierwsze i dzielniki.
- Różne czynniki pierwsze
- —
- Liczba dzielników
- —
Praktyczne zastosowania
Skracanie ułamków do najprostszej postaci. Weźmy ułamek 84/126. Rozkładamy licznik i mianownik osobno: 84 = 2^2 × 3 × 7, a 126 = 2 × 3^2 × 7. Teraz bierzemy z każdego czynnika pierwszego niższą z dwóch potęg, czyli dla 2 bierzemy 2^1 (niższa z 2^2 i 2^1), dla 3 bierzemy 3^1 (niższa z 3^1 i 3^2), a dla 7 bierzemy 7^1 (ta sama w obu). Wspólny czynnik to więc 2 × 3 × 7 = 42. Dzielimy licznik i mianownik przez 42: 84/42 = 2, a 126/42 = 3. Ułamek 84/126 w najprostszej postaci to 2/3. To ta sama metoda, którą stosuje się przy szukaniu NWD dwóch liczb, tyle że tutaj wynik od razu wykorzystujemy do skrócenia.
Znajdowanie wszystkich dzielników liczby. Rozkład na czynniki pierwsze pozwala policzyć, ile dzielników ma dana liczba, bez wypisywania ich po kolei metodą prób i błędów. Dla 360 = 2^3 × 3^2 × 5^1 bierzesz każdy wykładnik, dodajesz do niego 1, i mnożysz wyniki: (3+1) × (2+1) × (1+1) = 4 × 3 × 2 = 24. Liczba 360 ma dokładnie 24 dzielniki: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180 i 360. Ten wzór działa dla dowolnej liczby, wystarczy znać jej rozkład na czynniki pierwsze, dlatego rozkład zwykle jest pierwszym krokiem, a nie celem samym w sobie.
Podstawa kryptografii RSA. Szyfrowanie RSA opiera się na tym, że pomnożenie dwóch dużych liczb pierwszych jest łatwe (komputer robi to w ułamku sekundy), ale odtworzenie tych dwóch liczb pierwszych z samego iloczynu, mając setki cyfr, jest obliczeniowo niepraktyczne nawet dla potężnych klastrów obliczeniowych. Klucz publiczny zawiera właśnie taki iloczyn n = p × q, a klucz prywatny wymaga znajomości p i q osobno. Dzielenie próbne, ta sama metoda co przy 360 czy 1001, teoretycznie też rozłożyłaby taką liczbę, tylko że przy liczbach pierwszych rzędu 150 cyfr zajęłoby to więcej czasu, niż istnieje wszechświat. Stąd rozmiar kluczy RSA rośnie z czasem, w miarę jak komputery i lepsze algorytmy faktoryzacji przyspieszają.
Częste błędy i przypadki brzegowe
Zero i jeden nie są ani liczbami pierwszymi, ani złożonymi. Liczba 1 ma tylko jeden dzielnik (samą siebie), a definicja liczby pierwszej wymaga dokładnie dwóch różnych dzielników, więc 1 odpada. Zero z kolei dzieli się przez każdą liczbę całkowitą bez wyjątku, co też nie pasuje do żadnej z dwóch kategorii, dlatego 0 nie ma w ogóle rozkładu na czynniki pierwsze.
Liczby ujemne rozkłada się na podstawie ich wartości bezwzględnej. Rozkład liczby -360 wygląda identycznie jak rozkład 360, po prostu ze znakiem minus doczepionym z boku, nie jako osobny czynnik pierwszy. Nie istnieją “ujemne liczby pierwsze”.
Najczęstszy błąd przy ręcznym dzieleniu próbnym to niewiedza, kiedy przestać próbować kolejnych dzielników. Zasada jest taka: testujesz liczby pierwsze tylko do pierwiastka kwadratowego z tego, co ci zostało, nie z liczby wyjściowej. Jeśli żaden dzielnik pierwszy do tego pierwiastka nie pasuje, to, co zostało, samo jest liczbą pierwszą i kończysz od razu, bez sprawdzania większych kandydatów. Przy 997 wystarczyło sprawdzić do 31, mimo że sama liczba ma trzy cyfry, właśnie z tego powodu.
Najczęściej zadawane pytania
Do czego właściwie służy rozkład na czynniki pierwsze? Najczęściej do skracania ułamków, liczenia NWD i NWW dwóch lub więcej liczb, upraszczania pierwiastków oraz sprawdzania, czy liczba jest pierwsza. Poza matematyką szkolną ta sama idea, tylko na dużo większą skalę, jest podstawą bezpieczeństwa szyfrowania RSA.
Jak poznać, że liczba jest pierwsza, patrząc na nią? Bez dzielenia się tego nie da wiarygodnie stwierdzić, poza kilkoma prostymi sygnałami: liczba parzysta większa od 2 nigdy nie jest pierwsza, liczba kończąca się na 0 lub 5 (poza samą 5) też odpada, a suma cyfr podzielna przez 3 wyklucza podzielność przez 3. Poza tymi skrótami jedyna pewna metoda to dzielenie próbne aż do pierwiastka kwadratowego z liczby, tak jak pokazano wyżej dla 997.
Jaka jest największa liczba, którą można rozłożyć ręcznie? Zależy głównie od cierpliwości, nie od jakiegoś twardego limitu. Liczby czterocyfrowe, jak 1001, są w pełni wykonalne na kartce w kilka minut. Powyżej sześciu, siedmiu cyfr dzielenie próbne ręczne robi się mozolne, bo trzeba sprawdzić coraz więcej kandydatów na dzielniki, i w praktyce wygodniej sięgnąć po kalkulator, który wykonuje te same kroki dużo szybciej.
Czy rozkład na czynniki pierwsze danej liczby jest zawsze tylko jeden? Tak, i to jest istotny fakt, nazywany zasadniczym twierdzeniem arytmetyki. Każda liczba całkowita większa od 1 ma dokładnie jeden rozkład na czynniki pierwsze, jeśli pominąć kolejność zapisu czynników. Niezależnie od tego, czy zaczniesz dzielenie próbne od 2, czy od jakiejkolwiek innej liczby pierwszej, dojdziesz zawsze do tego samego wyniku końcowego.
Czy 1 lub 0 mogą być jednym z czynników w rozkładzie? Nie. Rozkład na czynniki pierwsze z definicji korzysta wyłącznie z liczb pierwszych, a ani 1, ani 0 nie są liczbami pierwszymi. Dopisywanie jedynki do iloczynu nie zmieniłoby zresztą wyniku (mnożenie przez 1 nic nie robi), więc nie ma powodu jej tam umieszczać.