primfaktoriseringen

Primfaktoriseringen er prosessen med å skrive et heltall større enn 1 som et produkt av primtall, der primfaktorene kan gjenta seg og rekkefølgen ikke spiller noen rolle.

Det fundamentale teoremet i aritmetikk sier at hvert heltall n > 1 kan skrives entydig som et produkt av primtall, opphøyd i eksponenter, og oppføringen er unik opp til rekkefølgen av faktorene.

Notasjon og eksempel: Vi skriver n = p1^a1 p2^a2 ... pk^ak, hvor p_i er primtall og a_i er positive heltall. For eksempel er 60 = 2^2 · 3^1 · 5^1.

Metodegrunnlag: man bruker deling av n med primtall opp til sqrt(n) for å finne faktorene; Sieve of Eratosthenes kan brukes til å generere primtall for større faktorisering; en faktortrær illustrerer hvordan tallet bygges opp av primfaktorer.

Anvendelser: primfaktorisering brukes til å forenkle brøker, finne største felles faktor og minste fellesnevner, samt i kryptografi, der faktorisering av store tall er en viktig utfordring for sikkerheten.

Begrensninger og variasjoner: primfaktorisering gjelder positive heltall større enn 1; for negative tall inkluderer man faktorene -1 og primtallene, og tallet 1 har ingen primfaktorisering.