Czynnik pierwszy

Czynnik pierwszy danej liczby naturalnej złożonej – to dowolna liczba pierwsza, która dzieli daną. Na przykład jednym z czynników pierwszych liczby 20 jest 5.

Jedna z podstawowych obserwacji dotyczących liczb naturalnych mówi, że każda liczba naturalna większa od 1 jest albo pierwsza, albo ma przynajmniej jeden czynnik pierwszy. Wynika stąd dalej, że każda liczba naturalna większa od 1 jest pierwsza, lub daje się zapisać w postaci iloczynu liczb pierwszych. Twierdzenie to nazywane jest często podstawowym twierdzeniem arytmetyki.

Przedstawienie danej liczby złożonej w postaci iloczynu czynników pierwszych nazywamy rozkładem liczby na czynniki pierwsze. Rozkład ten jest jednoznaczny w tym sensie, że każde dwa rozkłady danej liczby na czynniki pierwsze różnią się tylko kolejnością czynników.

Na przykład: 20 = 2·2·5 = 5·2·2 = 2·5·2 = 2²·5.

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
  • 63 = 4·15 + 3 i 63 = 9·7, przy czym 7 = 4·1 + 3
• każda liczba naturalna postaci 6k + 5 jest albo pierwsza, albo ma przynajmniej jeden czynnik pierwszy tej postaci
  • 119 = 6·19 + 5 i 119 = 7·17, przy czym 17 = 6·2+5

Rozkład liczby naturalnej na czynniki pierwsze jest bardzo złożony obliczeniowo, co stanowi podstawę 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 $r$. Wówczas:

$r=2^{w_2}\cdot 3^{w_3}\cdot 5^{w_5}\cdot 7^{w_7}\cdot \dots,$
gdzie $w_p$ 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 kolejne dzielenie.

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
• algorytm faktoryzacji rho Pollarda

Linki zewnętrzne

• Strona umożliwiająca rozkład danej liczy na czynniki pierwsze (działa dla dużych liczb)