Rozkład liczby na czynniki pierwsze i wszystkie dzielniki

Jak przebiega rozkład

Dzielimy liczbę przez najmniejszą liczbę pierwszą, która ją dzieli, czyli zaczynamy od dwójki. Otrzymany iloraz dzielimy dalej tą samą liczbą, dopóki się da, a potem przechodzimy do kolejnej liczby pierwszej. Kończymy, gdy iloraz zejdzie do jedynki.

Dla trzystu sześćdziesięciu wychodzi kolejno: dwa, dwa, dwa, trzy, trzy, pięć. Zapisane z potęgami daje dwa do trzeciej razy trzy do kwadratu razy pięć. Obie postacie są poprawne, ale ta druga jest wygodniejsza do dalszych rachunków.

Kolejność, w jakiej znajdujemy czynniki, nie ma znaczenia dla wyniku. Zaczynając od sześciu razy sześćdziesiąt dojdziemy do tego samego zestawu liczb pierwszych co zaczynając od czterech razy dziewięćdziesiąt. To właśnie treść twierdzenia o jednoznaczności rozkładu.

Dlaczego wystarczy szukać do pierwiastka

Dzielniki chodzą w parach: jeżeli a dzieli n, to n podzielone przez a też je dzieli. Jedna liczba z każdej pary jest nie większa od pierwiastka z n, a druga nie mniejsza.

Gdyby obie były większe od pierwiastka, ich iloczyn przekroczyłby n, co jest niemożliwe. Dlatego szukając dzielników, wystarczy sprawdzić liczby do pierwiastka, a resztę dopisać z par. Dla trzystu sześćdziesięciu oznacza to sprawdzenie liczb tylko do osiemnastu.

Ta sama obserwacja decyduje o szybkości kalkulatora. Dla liczby bliskiej bilionowi trzeba sprawdzić milion dzielników zamiast biliona, i dlatego rozkład zajmuje ułamek sekundy zamiast godzin.

Przykłady rozkładów z liczbą dzielników

Kolumna z liczbą dzielników wylicza się wprost z wykładników rozkładu: każdy wykładnik zwiększamy o jeden i mnożymy wyniki. Dla trzystu sześćdziesięciu daje to cztery razy trzy razy dwa, czyli dwadzieścia cztery dzielniki, bez wypisywania choćby jednego z nich.

Powód jest prosty. Każdy dzielnik powstaje przez wybranie, w jakiej potędze wziąć każdy czynnik pierwszy: dwójkę można wziąć w potędze zerowej, pierwszej, drugiej albo trzeciej, czyli na cztery sposoby. Mnożymy liczby możliwości dla każdego czynnika i dostajemy liczbę wszystkich kombinacji.

Ostatnia kolumna rozróżnia liczby pierwsze, złożone i kwadraty liczb całkowitych. Kwadrat poznaje się po tym, że wszystkie wykładniki w rozkładzie są parzyste, a liczba dzielników wychodzi wtedy nieparzysta, bo jeden z nich nie ma pary.

Cechy podzielności, czyli skrót przed rachunkiem

Zanim zacznie się dzielić, warto sprawdzić cechy. Podzielność przez dwa i przez pięć widać po ostatniej cyfrze, przez cztery i osiem po dwóch i trzech ostatnich, a przez trzy i dziewięć po sumie cyfr. Te sześć reguł wyłapuje większość dzielników liczb spotykanych w zadaniach.

Siódemka nie ma prostej cechy i to ona najczęściej umyka. Liczby czterdzieści dziewięć, siedemdziesiąt siedem, dziewięćdziesiąt jeden i sto dziewiętnaście wyglądają na pierwsze, a żadna nią nie jest, bo wszystkie dzielą się przez siedem.

Cecha podzielności przez jedenaście jest mniej znana, ale równie prosta: liczymy osobno sumę cyfr na miejscach nieparzystych i parzystych, a potem sprawdzamy, czy ich różnica dzieli się przez jedenaście. Dla tysiąca trzystu czterdziestu dwóch różnica wynosi zero, więc liczba się dzieli.

Jedynka nie jest liczbą pierwszą

Liczba pierwsza z definicji ma dokładnie dwa różne dzielniki naturalne: jedynkę i samą siebie. Jedynka ma tylko jeden dzielnik, więc tego warunku nie spełnia i nie jest ani pierwsza, ani złożona.

Nie jest to formalny kaprys. Gdyby jedynkę uznać za pierwszą, rozkład przestałby być jednoznaczny, bo do każdego iloczynu dałoby się dopisać dowolnie wiele jedynek. Całe twierdzenie o jednoznaczności rozkładu straciłoby wtedy sens.

Z tego samego powodu kalkulator odrzuca jedynkę jako daną wejściową. Zera również, bo zero dzieli się przez każdą liczbę i jego rozkład nie istnieje.

Do czego rozkład się przydaje

Największy wspólny dzielnik odczytuje się z rozkładów obu liczb: bierzemy czynniki wspólne w najniższych występujących potęgach. Najmniejszą wspólną wielokrotność tak samo, tylko w potęgach najwyższych. Obie wartości liczy kalkulator NWD i NWW.

Skracanie ułamka sprowadza się do podzielenia licznika i mianownika przez ich największy wspólny dzielnik, a ten z kolei wynika z rozkładów. Dlatego rozkład jest zwykle pierwszym krokiem przy pracy z ułamkami zwykłymi.

Trzecie zastosowanie to wyłączanie czynnika spod pierwiastka. Pierwiastek z siedemdziesięciu dwóch upraszcza się, bo siedemdziesiąt dwa to dwa do trzeciej razy trzy do kwadratu, a każda para jednakowych czynników wychodzi przed znak pierwiastka. Rachunki na potęgach prowadzi kalkulator potęg i pierwiastków.

Suma dzielników i liczby doskonałe

Kalkulator podaje też sumę wszystkich dzielników. Dla trzystu sześćdziesięciu wynosi ona tysiąc sto siedemdziesiąt, przy czym liczy się w niej zarówno jedynkę, jak i samą liczbę.

Jeżeli suma dzielników mniejszych od samej liczby równa się tej liczbie, nazywamy ją doskonałą. Najmniejsze takie liczby to sześć, bo jeden plus dwa plus trzy daje sześć, oraz dwadzieścia osiem, bo jeden plus dwa plus cztery plus siedem plus czternaście daje dwadzieścia osiem.

Liczb doskonałych znamy do dziś bardzo niewiele i wszystkie są parzyste. Pytanie, czy istnieje choć jedna nieparzysta, pozostaje otwarte od ponad dwóch tysięcy lat i jest jednym z najstarszych nierozwiązanych problemów matematyki.

Zakres kalkulatora

Liczby przyjmujemy od dwóch do biliona. Przy górnej granicy najdłużej liczą się liczby, które same są pierwsze, bo trzeba wtedy wyczerpać wszystkie dzielniki aż do pierwiastka. Nadal zajmuje to jednak ułamek sekundy.

Lista dzielników w rozbiciu wyniku jest skrócona do czterdziestu pozycji, bo przy liczbach wysoce złożonych bywa ich kilkaset. Liczba dzielników i ich suma zawsze dotyczą pełnego zbioru, niezależnie od długości wyświetlonej listy.

Cechy podzielności sprawdzamy dla liczb od dwóch do dziesięciu, a w tabeli powyżej opisujemy dodatkowo jedenaście i dwadzieścia pięć. To zestaw wystarczający do zadań szkolnych.

Gdzie to stoi w podstawie programowej

Podstawa programowa dla klas czwartej do szóstej wymaga rozkładania na czynniki pierwsze liczb jedno lub dwucyfrowych. Zakres jest więc wąski, a kalkulator sięga znacznie dalej, bo sama metoda na to pozwala.

W tych samych klasach pojawia się szukanie wspólnych dzielników i wspólnych wielokrotności, również dla liczb jedno i dwucyfrowych. Liczba dzielników wyliczana z wykładników rozkładu nie należy już do materiału szkolnego i pojawia się raczej w zadaniach konkursowych.

Cechy podzielności są w podstawie obecne jako narzędzie wskazujące na istnienie dzielnika. Właśnie w tej roli pokazujemy je obok rozkładu, a nie jako osobny temat do wykucia.

Sito Eratostenesa i rozmieszczenie liczb pierwszych

Najstarsza metoda znajdowania liczb pierwszych polega na wypisaniu liczb od dwóch w górę i wykreślaniu wielokrotności. Zostawiamy dwójkę i skreślamy co drugą liczbę, zostawiamy trójkę i skreślamy co trzecią, i tak dalej. To, co przetrwa, jest zbiorem liczb pierwszych.

Metoda nosi imię Eratostenesa, bibliotekarza z Aleksandrii, i ma ponad dwa tysiące dwieście lat. Wykreślanie wystarczy prowadzić do pierwiastka z górnej granicy, z tego samego powodu, dla którego dzielniki sprawdzamy tylko do pierwiastka.

Liczb pierwszych jest nieskończenie wiele, co udowodnił Euklides, ale rozkładają się coraz rzadziej. Wśród pierwszych stu liczb jest ich dwadzieścia pięć, wśród kolejnych stu już tylko dwadzieścia jeden, a w okolicach miliona średnio jedna na czternaście.

Ta rzadkość ma zastosowanie praktyczne. Współczesne szyfrowanie opiera się na tym, że pomnożyć dwie duże liczby pierwsze jest łatwo, a rozłożyć ich iloczyn z powrotem na czynniki bardzo trudno. To ta sama asymetria, którą widać w kalkulatorze: liczba złożona rozkłada się natychmiast, a liczba pierwsza bliska górnej granicy wymaga przejścia przez wszystkie dzielniki do pierwiastka.

Powiązane narzędzia

Zapis liczb w innych systemach pozycyjnych, gdzie podzielność wygląda zupełnie inaczej, obsługuje konwerter systemów liczbowych. Liczba parzysta ma tam zawsze zero na końcu zapisu dwójkowego.

Pozostałe narzędzia szkolne zbiera dział matematyczny.