Rozkład liczby (złożonej) na czynniki pierwsze polega na zapisaniu tej liczby w postaci iloczynu liczb (czynników) pierwszych.

Definicja 1

Czynnik pierwszy

Liczbę pierwszą p nazywamy czynnikiem pierwszym liczby naturalnej n\in\mathbb{N}, jeśli p jest dzielnikiem liczby n (p|n).

Twierdzenie 1

Rozkład liczby złożonej na czynniki pierwsze (zasadnicze twierdzenie arytmetyki)

Niech n będzie dowolną liczbą złożoną. Wówczas istnieje dokładnie jeden ciąg liczb pierwszych p_1<p_2<\ldots<p_k taki że:

(0)n=p_1^{n_1}\cdot p_2^{n_2}\cdots p_k^{n_k}=\prod_{i=1}^{k}p_i^{n_i},

gdzie n_i\in {\mathbb{N}_+}.

Przykład 1

Rozkład liczby na czynniki pierwsze

Zobaczmy jak wygląda rozkład liczby na ich czynniki pierwsze na kilku przykładach:

(0)\begin{align*} 4&=2\cdot 2\\ 12&=2\cdot 2\cdot 3=2^2\cdot 3\\ 15&=3\cdot 5\\ 72&=2\cdot 2\cdot 2\cdot 3 \cdot 3=2^3\cdot 3^2\\ 115&=5\cdot 23\\ 210&=2\cdot 3\cdot5\cdot 7 \end{align*}

Uwaga 1

Unikalność rozkładu na czynniki pierwsze

Zauważ, że zgodnie Twierdzeniem 1, dla każdej liczby złożonej istnieje dokładnie jeden rozkład liczby na czynniki pierwsze.

Dodatkowo, rozkład ten składa się z co najmniej dwóch czynników pierwszych.

W naszym przykładzie dostaliśmy rozkład:

(0)72=2^3\cdot 3^2,

w którym czynnik pierwszy 2 występuje trzykrotnie, natomiast czynnik pierwszy 3 - dwukrotnie. NIE ISTNIEJE inny rozkład liczby 72 składający się z innych liczb pierwszych, bądź tych samych liczb pierwszych lecz o innej częstotliwości występowania!

Algorytm rozkładania liczby na czynniki pierwsze

Aby rozłożyć liczbę na czynniki pierwsze, należy sukcesywnie dzielić ją przez najmniejsze liczby pierwsze, aż uzyskamy iloraz równy 1. Każdy dzielnik, przez który dzielimy liczbę, stanowi jeden z czynników pierwszych. Proces ten powtarzamy dla każdego kolejnego ilorazu, aż do momentu, gdy nie można już dokonać dalszego dzielenia.

Zasadnicze twierdzenie arytmetyki