AlegsaOnline.com

Fundamentalsætningen i aritmetik: definition og primfaktorisering

Lær fundamentalsætningen i aritmetik: unik primfaktorisering, metoder til faktorisering og betydning i talteori og kryptografi — klar, præcis forklaring med eksempler.

Forfatter: Leandro Alegsa Oprettelsesdato: 18. januar 2022 Seneste opdatering: 8. januar 2026

en.wikipedia.org · Public domain

Aritmetikkens fundamentalsætning (også kaldet den unikke faktoriseringssætning) er en sætning i talteori. Sætningen siger, at ethvert positivt heltal større end 1 kan skrives som et produkt af primtal (eller at heltallet i sig selv er et primtal). Sætningen siger også, at der kun er én måde at skrive tallet på. Hvis to personer finder to forskellige måder at skrive tallet på, er det eneste, der kan være forskelligt, den rækkefølge, i hvilken primtalene skrives. At finde primtalene kaldes faktorisering.

6936 = 2³ · 3 · 17² eller 1200 = 2⁴ · 3 · 5²

Hvad betyder "unik"?

Unikheden betyder, at ethvert heltal n > 1 kan skrives på formen

n = p₁^a1 · p₂^a2 · ... · p_k^ak

hvor p₁, p₂, ..., p_k er primtal og a1, a2, ..., ak er positive heltal. Denne repræsentation er entydig op til rækkefølgen af primtallene; man kan for eksempel altid vælge at skrive primtallene i stigende rækkefølge for at få en kanonisk form.

Eksistens og idékort bevis

Der er to dele i sætningen: eksistens (at enhver heltal > 1 kan faktoriseres i primtal) og unikhed (at denne faktorisering er entydig bortset fra rækkefølgen).

Eksistens: Bevises typisk ved fuldstændig induktion: hvis et tal er primt, er det allerede faktoriseret; hvis det er sammensat, kan det skrives som et produkt af to mindre positive heltal, og antagelsen om mindre tal giver primfaktorisering for hver faktor.
Unikhed: Bevises ved hjælp af Euclids lemma (hvis et primtal p deler produktet ab, må p dele a eller p dele b). Ved at anvende dette lemmas gentagne gange kan man vise, at to forskellige primfaktoriseringer nødvendigvis må indeholde de samme primtal med de samme eksponenter.

Praktisk primfaktorisering

Den mest direkte metode til at faktorisere et tal er trial division: prøv at dividere med små primtal (2, 3, 5, 7, 11 osv.) og fortsæt, indtil resten bliver 1. For meget store tal anvendes mere avancerede algoritmer (f.eks. Pollards rho, kvadratiske sigte, eller general number field sieve).

Faktoriseringens sværhedsgrad for store tal er grundlaget for sikkerheden i mange kryptografiske systemer — specielt RSA — fordi det er let at multiplicere store primtal, men vanskeligt at finde primfaktorerne, hvis tallet er meget stort.

Anvendelser og konsekvenser

Grundlaget for beregning af største fælles divisor (ggd) og mindste fælles multiplum (mkm) ud fra primfaktorer: ggd tager de fælles primtals mindste eksponent, mkm tager de største eksponent.
Vigtigt i studiet af diofantiske ligninger, modulær aritmetik og algebraiske strukturer som unikke faktoriseringsdomæner.
Direkte anvendt i kryptografi, især i nøgleskemaer hvor sikkerheden bygger på vanskeligheden ved primfaktorisering.

Bemærkninger

Tallet 1 er en særtilfælde: det har ingen primfaktorer og betragtes ofte som produktet af ingen primtal (den tomme produkt), så sætningen gælder for n > 1.
Negativt hele tal kan faktoreres ved at medtage -1: for eksempel -30 = -1 · 2 · 3 · 5.
Begrebet generaliseres i abstrakt algebra til unikke faktoriseringsdomæner (UFD), hvor elementer har unikke faktorisationer op til enhed og rækkefølge.

Hvis du vil øve primfaktorisering, kan du starte med tal som 360 = 2³ · 3² · 5 eller 2024 = 2³ · 11 · 23 og følge trial division-trinnene for at få erfaring med metoden.

Bevis

Den første person, der beviste sætningen, var Euklid. Det første detaljerede og korrekte bevis blev fundet i Disquisitiones Arithmeticae af Carl Friedrich Gauß.

Nogle mennesker tror måske, at sætningen er sand overalt. Sætningen er imidlertid ikke sand i mere generelle talsystemer, som f.eks. algebraiske heltal. Dette blev første gang nævnt af Ernst Kummer i 1843 i hans arbejde om Fermats sidste sætning. For yderligere oplysninger om dette: læs algebraisk talteori.

Beviset består af to dele: først viser vi, at ethvert tal kan skrives som et produkt af primtal; dernæst viser vi, at hvis vi skriver et tal som et produkt af primtal for anden gang, så må de to lister over primtal være de samme.

Første del af beviset

Vi viser, at hvis ikke alle tal større end 1 kan skrives som et produkt af primtal, ender vi i en slags umulighed. Så herefter konkluderer vi, at det må være sandt, at alle tal kan skrives som et produkt af primtal.

Så se nu, hvad der sker, når nogen siger, at han/hun kender et positivt heltal, der er større end 1, som ikke kan skrives som et produkt af primtal. I så fald beder vi ham/hende om at nævne alle de tal, der er større end 1, som ikke kan skrives som et produkt af primtal. Et af disse tal skal være det mindste af dem: vi kalder det n. Naturligvis kan dette tal n ikke være 1. Det kan heller ikke være et primtal, for et primtal er et "produkt" af et enkelt primtal: sig selv. Det skal altså være et produkt af tal. Således-

n = ab

hvor både a og b er positive hele tal, der naturligvis er mindre end n. Men: n var det mindste tal, der ikke kan skrives som et produkt af primtal. Så det må være muligt at skrive a og b som produkter af primtal, fordi de begge er mindre end n. Men så er produktet

n = ab

kan også skrives som et produkt af primtal. Dette er en umulighed, fordi vi sagde, at n ikke kan skrives som et produkt af primtal.

Vi har nu vist, at det er umuligt, hvis den første del af sætningen ikke er sand. På denne måde har vi nu bevist den første del af sætningen.

Anden del af beviset

Nu skal vi bevise, at der kun er én måde at skrive et positivt tal større end 1 på som et produkt af primtal.

Til dette formål bruger vi følgende lemma: Hvis et primtal p deler et produkt ab, så deler det enten a eller b (Euklids lemma). Først skal vi nu bevise dette lemma. Godt, antag nu, at p ikke deler a. Så er p og a coprime, og vi har Bezout's identitet, der siger, at der må være hele tal x og y, således at

px + ay = 1.

Multiplikation af alt med b giver

pbx + aby = b,

Husk, at ab kunne deles med p. Så nu har vi på venstre side to termer, der er delelige med p. Så termen på højre side er også delelig med p. Vi har nu bevist, at hvis p ikke deler a, må det dele b. Det beviser lemmaet.

Nu skal vi bevise, at vi kun kan skrive et heltal større end 1 på én måde som et produkt af primtal. Tag to produkter af primtal A og B, som har samme resultat. Vi ved altså for produkternes udfald, at A = B. Tag et vilkårligt primtal p fra det første produkt A. Det deler A, så det deler også B. Ved flere gange at bruge det lemma, vi lige har bevist, kan vi se, at p så må dele mindst én faktor b af B. Men faktorerne er alle primtal selv, så også b er primtal. Men vi ved, at p også er primtal, så p må være lig med b. Så nu dividerer vi A med p og dividerer også B med p. Og vi får et resultat som A* = B*. Igen kan vi tage et primtal p fra det første produkt A* og finde ud af, at det er lig med et tal i produktet B*. Hvis vi fortsætter på denne måde, kan vi til sidst se, at primfaktorerne i de to produkter må være nøjagtig ens. Dette beviser, at vi kun kan skrive et positivt heltal som et produkt af primtal på én enkelt måde.

Relaterede sider

Grundlæggende sætning i algebra

Mængder af hele tal baseret på delbarhed
Oversigt	Faktorisering af heltal Divisor Enhedsdivisoren Divisorfunktion Primusfaktor Grundlæggende sætning i aritmetik
Factoriseringsformer	Prime Komposit Semiprime Pronic Sphenic Firkantet fri Kraftfuld Perfekt effekt Achilles Glat Almindelig Rough Usædvanligt
Begrænsede divisorsummeringer med begrænsninger	Perfekt Næsten perfekt Quasiperfect Multiplicere perfekt Hemiperfect Hyperperfekt Superperfekt Enhedsmæssig perfekt Semiperfekt Praktisk Erdős-Nicolas
Med mange divisorer	Overflødig Primitiv rigelig Meget rigeligt Overflødig Kolossalt rigeligt Meget sammensat Superior meget sammensat Mærkeligt
Aliquot-sekvensrelateret	Uantastelig Amicable (tredobbelt) Sociable Forlovet
Baseafhængig	Equidigital Ekstravagant Frugal Harshad Polydivisible Smith
Andre sæt	Aritmetik Mangelfuld Venlig Ensomme Sublim Harmonisk divisor Descartes Refactorable Superperfekt

Spørgsmål og svar

Spørgsmål: Hvad er den grundlæggende sætning i aritmetik?

A: Aritmetikkens fundamentale sætning er en sætning i talteori, der siger, at ethvert positivt heltal større end 1 kan skrives som et produkt af primtal, og at der kun er én måde at skrive tallet på.

Spørgsmål: Hvordan kan dette teorem bruges?

Svar: Denne sætning kan bruges i kryptografi.

Spørgsmål: Hvad sker der, hvis to personer finder to forskellige måder at skrive det samme tal på?

Svar: Hvis to personer finder to forskellige måder at skrive det samme tal på, er det eneste, der kan være forskelligt, den rækkefølge, hvori primtalene er skrevet.

Spørgsmål: Hvad er faktorisering?

A: Faktorisering er at finde alle de primtal, der udgør et givet tal.

Spørgsmål: Er 6936 et eksempel på et primtal?

Svar: Nej, 6936 er ikke et primtal; det kan skrives som 23 - 3 - 172.

Nej, 6936 er ikke et primtal; det kan skrives som 23 - 3 - 172.