Delbarhet og faktorisering

Det kanskje viktigste grunnlaget i tallteorien er hvordan de hele tallene kan faktoriseres og uttrykkes som produkter av primtall. Mange av de største resultatene i tallteoripensumet i Matematikk X kommer blant annet i fra det vi her skal finne ut om faktorisering og primtall.

Faktorer og delelighet

Når vi bare arbeider med hele tall, er det ikke alltid vi kan dele et tall på et annet og få et nytt helt tall. Hvis vi for eksempel har en klasse med 23 elever, er det ikke så lett å dele denne i to like store grupper -- tallet 23 er ikke delelig på 2.

Hvis et tall <math>a</math> kan skrives som et produkt <math>a = bc</math> så sier vi at <math>b</math> og <math>c</math> er faktorer i <math>a</math>. En kortere skrivemåte for å si at <math>b</math> og <math>c</math> er faktorer i <math>a</math> er <math>b | a</math> og <math>c | a</math>. Vi kan lese slike utsagn <math>a | b</math> på flere måter, som er oppsummert under:

Ekvivalente utsagn om faktorer og delelighet

Dersom heltallet <math>a</math> er en faktor i heltallet <math>b</math> skriver vi dette som <math>a | b</math>, og det betyr akkurat det samme som:
<math>a</math> deler <math>b</math>

<math>a</math> går opp i <math>b</math>

<math>b</math> er delelig på <math>a</math>

De forskjellige utsagnene i boksen ovenfor er nok kjent for mange, men det er viktig å merke seg at alle sammen betyr det samme. Hvis 3 er en faktor i 12 så kan vi like gjerne si at 3 deler 12, at 3 går opp i 12, eller at 12 er delelig på 3. Hva vil det si at et tall er delelig på et annet?

Delelighet

Dersom et tall <math>a</math> deler et tall <math>b</math> eller sagt på en annen måte, at tallet <math>b</math> delelig på <math>a</math> så må tallet <math>\frac{b}{a}</math> være et helt tall.

Eksempel

Vi har at <math>12 = 3 \cdot 4</math>. Da kan vi si at <math>3 | 12</math> og <math>4 | 12</math>, eller med andre ord at 12 er delelig på 3 og 4. Når vi deler 12 på 3 eller 4 så får vi et helt tall.

Når vi arbeider med tallteori er det ofte nyttig å ha en annen måte å uttrykke delelighet på utenom forskjellige måter å ordlegge det på. Vi kan også uttrykke at et tall er faktor i et annet på følgende måte:

Dersom <math>a | b</math> så må det finnes et helt tall <math>k</math> som er slik at

<math>b = k \cdot a</math>

Hvis <math>a</math> skal være en faktor i <math>b</math> må det jo nettopp være slik at <math>b</math> er produktet av <math>a</math> og et eller annet tall <math>k</math>, der <math>k</math> da blir resten av faktorene som utgjør tallet <math>b</math>.

Eksempel

<math>5</math> er en faktor i <math>30</math>, for vi kan dele <math>30</math> på <math>5</math> og få heltallet <math>6</math>. Vi har at <math>30</math> kan skrives som

<math>30 = 5 \cdot 6</math>

og dette er på formen <math>30 = 5 \cdot k</math>, der <math>k = 6</math>.

Her er noen av de mest grunnleggende egenskapene ved delelighet:

Grunnleggende regler for delelighet

For alle heltall <math>a</math> gjelder følgende:

<math>1 | a</math>

<math>a | a </math>

<math>a | 0</math>

Hvis <math>a | b</math> og <math>b | c</math> så vil <math>a | c</math>

<math>a | b</math> og <math>b | a</math> hvis og bare hvis <math>a = \pm b</math>

Hva sier reglene i boksen ovenfor? De tre første kjenner de fleste fra barne- eller ungdomsskolen. Tallet 1 deler alle tall. Vi kan dele et hvilket som helst tall på 1, og da får vi ut tallet selv. Utsagnet på den andre linjen sier at et tall <math>a</math> alltid er delelig med seg selv. Hvis vi deler et tall på seg selv får vi jo det hele tallet 1, så dette må stemme. Den tredje linjen sier at 0 er delelig på alle tall. Dette stemmer også, siden vi kan dele 0 på hva som helst, og da får vi 0, som er et helt tall.

De to siste egenskapene kan virke litt mindre elementære, men de er også ganske greie når vi ser litt nøyere på hva de sier. Den fjerde linja sier at hvis <math>a</math> er en faktor i <math>b</math> og <math>b</math> er en faktor i <math>c</math>, så må a også være en faktor i <math>c</math>. Se på noen tall og se om du får det til å stemme!

Den nederste egenskapen sier at dersom to tall er faktorer i hverandre så må de enten være like hverandre, eller motsatt like store av hverandre.

Primtallsfaktorisering

Hvis man ser på noen heltall vil man raskt oppdage at noen tall har flere faktorer, mens andre ikke har noen andre enn seg selv og 1. Vi kaller førstnevnte type tall for sammensatte tall. Tallene som bare har seg selv og 1 som faktor kaller vi primtall. Et viktig resultat i tallteorien er at primtallene er byggesteinene for alle andre tall:

Aritmetikkens fundamentalsetning

Et hvert tall <math>n > 1</math> kan skrives entydig som et produkt av primtall, når vi ser bort i fra rekkefølgen til faktorene.

Bevis

Aritmetikkens fundamentalteorem sier altså at du alltid kan faktorisere et tall til et produkt av primtall. Det sier videre at du bare kan gjøre dette på én måte (når vi ser bort i fra rekkefølgen til faktorene.) Aritmetikkens fundamentalsetning sier ingenting om hvordan vi gjør dette, bare at det alltid går an. Å utføre selve faktoriseringen gjør vi ved å finne hvilke primfaktorer tallet vi skal faktorisere er delelig med. Når vi deler på denne faktoren får vi de resterende faktorene i tallet. Dette kan vi gjenta helt til vi står igjen med et primtall. Dette er best vist ved et eksempel:

Eksempel:

Faktoriser tallet 162 til et produkt av primtall.

Vi prøver først å dele på 2. Divisjonen går opp og vi får 81. Da har vi at
<math>2 | 162</math>.

Vi fortsetter med tallet 81. Vi prøver å dele på 2, men det går ikke. Neste primtall er da 3. Deler vi 81 på 3 får vi 27, så
<math>3 | 81</math>.

Vi fortsetter med 27 og prøver igjen å dele på 3. Dette går opp, og vi får 9.
<math>3 | 27</math>.

Vi fortsetter med 9 og prøver igjen å dele på 3. Nå får vi 3, så
<math>3 | 9</math>.

Vi fortsetter med 3 og prøver enda en gang å dele på 3. Da får vi 1, så
<math>3 | 3</math>.

Nå står vi igjen med tallet 1, som ikke er et sammensatt tall. Da er vi ferdige. I hver linje ovenfor vil tallet til venstre være en faktor i 162. Vi har altså funnet at
<math>162 = 2 \cdot 3 \cdot 3 \cdot 3 \cdot 3</math>.

Aritmetikkens fundamentalsetning garanterer oss at dette også er den eneste måten vi kan faktorisere tallet på, hvis vi ser borti fra hvilken rekkefølge faktorene står i.