Bevis av aritmetikkens fundamentalsetning

Setning Et hvert tall <math>n > 1</math> kan skrives som et entydig produkt av primtallsfaktorer.

---

Bevis:

Dersom <math>n</math> er et primtall så er det ingenting å bevise. Derfor antar vi videre at <math>n</math> er et sammensatt tall. Da er det to ting vi er nødt til å bevise:

1. At et hvert tall alltid kan faktoriseres til et produkt av primtall
2. At det bare fins én måte å gjøre dette på.

Vi begynner med steg 1.

Siden tallet <math>n</math> er sammensatt, har det en minste faktor <math>d</math>, der <math>1 < d < n</math>. Denne faktoren er nødt til å være et primtall. Hvis ikke er <math>d</math> sammensatt, og inneholder en faktor <math>k</math> der <math>1 < k < d</math>. Men siden <math>k | d</math> og <math>d | n</math>, så må <math>k | n</math>, og da er <math>k</math> den minste faktoren i <math>n</math>, noe som strider i mot vårt valg av <math>d</math> som den minste faktoren i <math>n</math>. Dermed kan vi anta at <math>d</math> er et primtall, og vi kan kalle dette tallet for <math>p_1</math>. Nå kan vi skrive <math>n</math> som:

<math>n = p_1 \cdot n_1</math>

der <math>n_1</math> er produktet av de faktorene i <math>n</math> som er igjen etter at vi tok ut primfaktoren <math>p_1</math>. Vi kan gjenta akkurat den samme prosedyren som ovenfor på <math>n_1</math> og få en ny primfaktor <math>p_2</math> og et nytt tall <math>n_2</math> som er resten av faktorene i <math>n</math> etter at både <math>p_1</math> og <math>p_2</math> er tatt ut. Vi kan gjenta prosessen flere ganger, men vi kan ikke fortsette slik evig, for hvert av tallene <math>n_1, n_2, n_3, ...</math> er slik at

<math>n > n_1 > n_2 > n_3 > n_4 > ... > 1</math>

siden hvert tall i denne ulikheten oppstår ved at vi tar ut en primfaktor fra det forgående tallet. Til slutt må vi altså komme ned til at vi står igjen med 1, og da er vi ferdige. Vi står da igjen med at <math>n</math> kan skrives som primtallsproduktet

<math>n = p_1 \cdot p_2 \cdot p_3 \dots p_k</math>

Nå har vi altså vist at et sammensatt tall <math>n</math> alltid kan faktoriseres til et produkt av primtall. Men vi har ikke vist at det bare er mulig å finne én kombinasjon av primtall som gir tallet <math>n</math> når vi multipliserer dem sammen.

Vi fortsetter med steg 2:

Når vi skal vise en påstand så kan dette gjøres ved et såkalt motsigelsesbevis.

Her beviser vi at det kun er én måte å faktorisere tallet på, ved å utføre et slikt motsigelsesbevis. Vi antar at det finnes flere måter å faktorisere et sammensatt tall som et produkt av primtall. Det betyr at

<math>n = p_1 \cdot p_2 \cdot p_3 \dots p_k</math>

<math>n = q_1 \cdot q_2 \cdot q_3 \dots q_r</math>,

der hver av <math>p</math>-ene og <math>q</math>-ene er primtall, og primtallene er ordnet etter størrelse, sånn at

<math>p_1 \leq p_2 \leq p_3 \leq ... \leq p_k \quad \text{og} \quad q_1 \leq q_2 \leq q_3 \leq ... \leq q_r</math>

Kort sagt: det vi antar er at vi kan gange sammen <math>k</math> primtall og få <math>n</math>, og at vi kan gange sammen <math>r</math> stykker primtall som ikke nødvendigvis er de samme som de første, og også få tallet <math>n</math>. Nå må vi se på hva som skjer når vi antar dette.

Siden de to primtallsproduktene begge skal gi tallet <math>n</math>, så må begge produktene være like. Da har vi altså at

<math>p_1 \cdot p_2 \cdot p_3 \dots p_k = q_1 \cdot q_2 \cdot q_3 \dots q_r</math>

Siden vi har et primtall <math>p_1</math> på venstre side, må vi også finne dette primtallet igjen på høyre side. Tallet <math>p_1</math> kan vi jo ikke få ved å multiplisere sammen noen av tallene på høyre side -- det er jo et primtall. Vi har da at

<math>p_1 \geq q_1</math>

(enten er <math>p_1</math> lik faktoren <math>q_1</math>, eller så er det et av <math>q_2, q_3, ..., q_r</math>, og da er det større enn <math>q_1</math>.)

Men hvis vi nå ser på høyre siden så har vi her en faktor <math>q_1</math>, og av akkurat samme argumentasjon så må denne være en av faktorene på venstre side. Vi får da at

<math>q_1 \geq p_1</math>

Nå har vi to ulikheter som involverer <math>p_1</math> og <math>q_1</math>. Begge to vil kun være oppfylt når <math>p_1 = q_1</math>. Men da har vi to like faktorer på hver side av ligningen og vi kan forkorte <math>p_1</math> mot <math>q_1</math>. Da får vi:

<math>p_2 \cdot p_3 \dots p_k = q_2 \cdot q_3 \dots q_k</math>

Men nå kan vi gjøre akkurat det samme for <math>p_2</math> og <math>q_2</math>. Slik kan vi fortsette. Det vil eventuelt oppstå et av to tilfeller. Dersom det er like mange faktorer på hver side i ligningen, det vil si at <math>k = r</math> så er vi ferdige, for da har vi vist at <math>p_i = q_i</math> for alle <math>i</math> fra og med 1 til og med <math>k</math>. Det betyr at de to faktoriseringene er identiske, og altså ikke forskjellige likevel.

Det andre tilfellet er at <math>k \neq r</math>. Vi må undersøke videre hva som skjer når det er tilfellet. Da får vi bruk for en bevisteknikk som kalles bevis ved selvmotsigelse. Da starter vi med å anta at det vi skal vise ikke er sant, og så viser vi at det fører til noe som vi vet er galt. Hvis alle steg i bevisføringen da er riktig, er det nødt til å være antagelsen som er gal -- og hvis antagelsen er gal, er det motsatte av antagelsen riktig. Så hvis vi antagelsen er at det ikke stemmer, må resultatet bli at det stemmer.

Vi begynner med å anta at <math>k \neq r</math>. Da antar vi at <math>r > k</math>. Da ser vi på ligningen vår:

<math>p_1 \cdot p_2 \cdot p_3 \dots p_k = q_1 \cdot q_2 \cdot q_3 \dots q_r</math>

Som vist ovenfor vil <math>p_i = q_i</math> for alle <math>1 \geq i \geq k</math>. På venstre side av ligningen vil vi da ha forkortet alle faktorene, og står igjen med 1. På høyre side forkorter vi alle faktorene fra <math>q_1</math> opp til <math>q_k</math>. Da står vi igjen med faktorene fra og med <math>q_{k+1}</math> til og med <math>q_r</math>. Men da har vi ligningen:

<math>1 = q_{k+1} \cdot q_{k+2} \dots q_r</math>

Dette er umulig -- tallet 1 kan ikke være lik produktet av ett eller flere primtall. Da må antagelsen om at <math>k \neq r</math> være gal, altså er <math>k = r</math> eneste mulighet.

Dette fullfører beviset.