Czynnik pierwszy – dowolna liczba pierwsza, która dzieli bez reszty daną liczbę naturalną złożoną. Na przykład jednym z czynników pierwszych liczby 20 jest 5.
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 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 ![{\displaystyle 7=4\cdot 1+3;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4a355f9475d010ecb9d7903be79ac32410f1f9d4)
- każda liczba naturalna postaci 6k + 5 jest albo pierwsza, albo ma przynajmniej jeden czynnik pierwszy tej postaci
i
przy czym ![{\displaystyle 17=6\cdot 2+5.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eb5438fc9741389e1ecdd03cc975088345ebef61)
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 można też jednoznacznie wykonać dla dowolnej dodatniej liczby wymiernej
Wówczas:
![{\displaystyle r=2^{w_{2}}\cdot 3^{w_{3}}\cdot 5^{w_{5}}\cdot 7^{w_{7}}\cdot \ldots ,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5d6af135c61aca026a450187eaab5a5220107dcf)
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.:
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ż
Linki zewnętrzne