Czynnik pierwszy


Czynnik pierwszy w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

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: 20 = 2 2 5 = 5 2 2 = 2 5 2 = 2 2 5. {\displaystyle 20=2\cdot 2\cdot 5=5\cdot 2\cdot 2=2\cdot 5\cdot 2=2^{2}\cdot 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 {\displaystyle 63=4\cdot 15+3} i 63 = 9 7 , {\displaystyle 63=9\cdot 7,} przy czym 7 = 4 1 + 3 ; {\displaystyle 7=4\cdot 1+3;}
  • każda liczba naturalna postaci 6k + 5 jest albo pierwsza, albo ma przynajmniej jeden czynnik pierwszy tej postaci
    • 119 = 6 19 + 5 {\displaystyle 119=6\cdot 19+5} i 119 = 7 17 , {\displaystyle 119=7\cdot 17,} przy czym 17 = 6 2 + 5. {\displaystyle 17=6\cdot 2+5.}

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

Rozkład na czynniki pierwsze można też jednoznacznie wykonać dla dowolnej dodatniej liczby wymiernej r . {\displaystyle r.} Wówczas:

r = 2 w 2 3 w 3 5 w 5 7 w 7 , {\displaystyle r=2^{w_{2}}\cdot 3^{w_{3}}\cdot 5^{w_{5}}\cdot 7^{w_{7}}\cdot \ldots ,}
gdzie w p {\displaystyle 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 kod

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

Linki zewnętrzne | edytuj kod

Na podstawie artykułu: "Czynnik pierwszy" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy