Czynnik pierwszy

Z Wikipedii, wolnej encyklopedii
(Przekierowano z Czynniki pierwsze)
Skocz do: nawigacja, szukaj

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 = 22·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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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ż[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]