Encyklopedia w Markpol

Reklama:

Czynnik pierwszy danej liczby naturalnej złożonej, to dowolna liczba pierwsza, która dzieli tę liczbę. 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 albo pierwsza, albo daje się zapisać w postaci iloczynu liczb pierwszych. Przestawienie 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. Kilka faktów o postaci czynników pierwszych:
  • 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 ma niebagatelne znaczenie dla kryptografii (patrz np. klucz RSA).

    Zobacz też

  • rho Pollarda

    Chcesz wypromować swoją stronę w internecie?? - nie zwlekaj pozycjonowanie w Luman.biz to rozsądny wybór
    2005 Encyklopedia
    These materials are based onWikipedia and licensed under the GNU FDL
    Loans|Video Games|Free Advertising|Mortgage|Virtual Private Server