mały|Diagram Hassego przedstawiający rozkład na czynniki liczby 42 mały|Inny diagram Hassego przedstawiający rozkład liczby 42 na czynniki – zaczyna się inaczej, ale kończy się jednakowymi czynnikami pierwszymi: 2,3,7
Czynnik pierwszy – dowolna liczba pierwsza, która dzieli bez reszty daną liczbę naturalną. Na przykład jednym z czynników pierwszych liczby jest liczba . Z kolei wszystkie czynniki pierwsze liczby , są stanowione łącznie przez liczby: , .
Jedna z podstawowych obserwacji dotyczących liczb naturalnych mówi: każda liczba naturalna większa od 1 jest albo pierwsza, albo ma przynajmniej jeden czynnik pierwszy. Z niej wynika kolejna: każda liczba naturalna większa od 1 jest pierwsza lub daje się zapisać w postaci iloczynu liczb pierwszych. Twierdzenie to nazywa się podstawowym twierdzeniem arytmetyki.
Przedstawienie danej liczby złożonej w postaci iloczynu czynników pierwszych nazywa się rozkładem liczby na czynniki pierwsze. Rozkład ten jest jednoznaczny w tym sensie, że wszystkie rozkłady danej liczby na czynniki pierwsze różnią się tylko ich kolejnością.
Na przykład, dla liczby możemy napisać następujący poprawny ciąg równości:
A zatem, dla liczby , jej czynnikami pierwszymi są liczby: (jest to czynnik występujący w maksymalnej potędze ), oraz (czynnik występujący w maksymalnej potędze ).
Dla czynników pierwszych prawdziwe są m.in. poniższe stwierdzenia: każda liczba złożona ma czynnik pierwszy, który nie przekracza pierwiastka kwadratowego z tej liczby; każda liczba naturalna postaci 4k + 3 jest albo pierwsza, albo ma przynajmniej jeden czynnik pierwszy tej postaci i , przy czym: każda liczba naturalna postaci 6k + 5 jest albo pierwsza, albo ma przynajmniej jeden czynnik pierwszy tej postaci i , przy czym:
Rozkład liczby naturalnej na czynniki pierwsze ma wysoką złożoność obliczeniową, co stanowi podstawę algorytmów stosowanych w kryptografii asymetrycznej (patrz np. klucz RSA).
Rozkład liczby wymiernej na czynniki
Rozkład na czynniki pierwsze (inaczej faktoryzacja z angielskiego factorization) można też jednoznacznie wykonać dla dowolnej dodatniej liczby wymiernej Wówczas:
gdzie są liczbami całkowitymi.
Taki rozkład ma duże znaczenie w teorii liczb, w szczególności służy do konstrukcji liczb p-adycznych.
Algorytm rozkładu na czynniki pierwsze Elementarnym sposobem rozkładu liczb na czynniki pierwsze jest wykonywanie kolejnych dzieleń, np.:
56|2 28|2 14|2 7|7 1|
Szukamy najmniejszej liczby pierwszej dzielącej daną liczbę (56). Jest to 2. Dzielimy: 56/2=28. Powtarzamy tę czynność dla kolejnych wyników aż do uzyskania w ilorazie liczby 1. Otrzymujemy wówczas wszystkie dzielniki pierwsze szukanej liczby. Na schemacie znajdują się one po prawej stronie.
Zobacz też
ideał pierwszy
Przypisy
Linki zewnętrzne [dostęp 2024-02-02]. Strona umożliwiająca rozkład danej liczy na czynniki pierwsze (działa dla dużych liczb)
Kategoria:Teoria liczb Kategoria:Dwuczłonowe relacje matematyczne Kategoria:Teoria podzielności