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
  • każda liczba naturalna postaci 6k + 5 jest albo pierwsza, albo ma przynajmniej jeden czynnik pierwszy tej postaci
    • i przy czym

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:


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.:

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ż

Linki zewnętrzne

  • Eric W. Weisstein, Prime Factor, [w:] MathWorld, Wolfram Research (ang.). [dostęp 2024-02-02].
  • Strona umożliwiająca rozkład danej liczy na czynniki pierwsze (działa dla dużych liczb)

Witaj

Uczę się języka hebrajskiego. Tutaj go sobie utrwalam.

Źródło

Zawartość tej strony pochodzi stąd.

Odsyłacze

Generator Margonem

Podziel się