Tallteori

1.1 Hva er tallteori?

Tallteori er en gren av matematikk som studerer egenskapene til heltall. Fagfeltet utforsker primtall, delbarhet, kongruenser og mange andre egenskaper ved tall.

1.2 Grunnleggende begreper

• Heltall: Tallene ..., -3, -2, -1, 0, 1, 2, 3, ...
• Naturlige tall: 1, 2, 3, ...
• Primtall: Et primtall er et heltall større enn 1 som bare er delelig med 1 og seg selv (f.eks. 2, 3, 5, 7, ...).
• Sammensatte tall: Et heltall større enn 1 som ikke er et primtall.

1.3 Delbarhet

• Definisjon: Et heltall a er delelig med et annet heltall b hvis det finnes et heltall k slik at a = bk.
• Eksempel: 12 er delelig med 3 fordi 12 = 3 × 4.

1.4 Euklids algoritme

Euklids algoritme er en effektiv metode for å finne den største felles divisor (GCD) av to tall.

Eksempel: Finn GCD(48,18):

1. 48 ÷ 18 = 2 rest 12
2. 18 ÷ 12 = 1 rest 6
3. 12 ÷ 6 = 2 rest 0
4. Siste ikke-null rest er 6, så GCD(48,18) = 6.

---

2.1 Primtallssetningen

Antallet primtall mindre enn en gitt verdi n kan estimeres med formelen: $\pi (n)\approx \frac{n}{\ln (n)}$

2.2 Eratosthenes' sil

En metode for å finne alle primtall opp til et gitt tall n:

1. Skriv opp alle tall fra 2 til n.
2. Stryk ut alle multipler av 2 (bortsett fra 2).
3. Finn neste ikke-strøkede tall, stryk ut alle dets multipler.
4. Gjenta til alle tall er behandlet.

Eksempel: Finn primtall opp til 30:

• Start: 2, 3, 4, ..., 30
• Stryk: 4, 6, 8, ..., 30 (multipler av 2)
• Stryk: 9, 15, 21, ... (multipler av 3)
• Stryk: 25 (multipler av 5)
• Primtallene er: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

2.3 Primtallsfaktorisering

Alle heltall større enn 1 kan skrives som et produkt av primtall.

Eksempel: Faktorisering av 84: $84=2\times 2\times 3\times 7$

---

Kapittel 3: Kongruensregning

3.1 Definisjon av kongruens

To tall a og b sies å være kongruente modulo n hvis n deler a - b: $a\equiv b(\mathrm{mod}n)$

Eksempel: 17 og 5 er kongruente modulo 6 fordi 17 - 5 = 12 er delelig med 6.

3.2 Lineære kongruenser

En lineær kongruens er en ligning av formen: $ax\equiv b(\mathrm{mod}n)$ Løsningen finnes ved å finne inversen til a modulo n.

Eksempel: Finn x slik at $3x\equiv 2(\mathrm{mod}7)$.

• Finn inversen til 3 modulo 7: $3^{-1}=5$ (fordi $3\times 5\equiv 1(\mathrm{mod}7)$).
• Multipliser begge sider med 5:

$x\equiv 10\equiv 3(\mathrm{mod}7)$

---

Moduloregning

Moduloregning er en gren av tallteori som omhandler kongruenser. Det brukes ofte i kryptografi, datavitenskap og algebra.

Grunnleggende begreper

Definisjon

Gitt to heltall $a$ og $b$, og et positivt heltall $n$, sier vi at $a$ er kongruent med $b$ modulo $n$, skrevet som:

$a\equiv b(\mathrm{mod}n)$

hvis $n$ deler differansen $a-b$, det vil si at det finnes et heltall $k$ slik at:

$a-b=kn$

Eksempel

Et eksempel på moduloregning er:

$17\equiv 5(\mathrm{mod}6)$

fordi $17-5=12$, og $12$ er delelig med $6$.

Egenskaper

Moduloregning følger flere viktige regler:

1. **Addisjon:** Hvis $a\equiv b(\mathrm{mod}n)$ og $c\equiv d(\mathrm{mod}n)$, så er også $a+c\equiv b+d(\mathrm{mod}n)$.
2. **Multiplikasjon:** Hvis $a\equiv b(\mathrm{mod}n)$, så er også $ac\equiv bc(\mathrm{mod}n)$ for alle heltall $c$.
3. **Potensiering:** Hvis $a\equiv b(\mathrm{mod}n)$, så er også $a^k\equiv b^k(\mathrm{mod}n)$ for alle heltall $k$.

Praktiske anvendelser

Moduloregning har mange anvendelser, inkludert:

• **Kryptografi** – Brukes i RSA-kryptering og andre krypteringsalgoritmer.
• **Datavitenskap** – Brukes i hashing og sirkulære datastrukturer.
• **Kalenderberegninger** – Bestemmelse av ukedager for en gitt dato.

Øvingsoppgaver

1. Finn den minste ikke-negative resten når $29$ deles på $7$.
2. Bestem $x$ slik at $x\equiv 3(\mathrm{mod}5)$ og $x\equiv 4(\mathrm{mod}7)$.
3. Beregn $2^{10}\mathrm{mod}13$.

Se også

• Tallteori
• Euklids algoritme
• RSA-kryptosystemet

Kapittel 4: Diophantiske ligninger

4.1 Lineære Diophantiske ligninger

En ligning av formen: $ax+by=c$ har heltallsløsninger hvis og bare hvis GCD(a, b) deler c.

Eksempel: Finn heltallsløsninger til $6x+9y=15$.

• GCD(6,9) = 3, som deler 15, så løsninger finnes.
• Ved Euklids algoritme finner vi x = 1, y = -1 som en spesiell løsning.

4.2 Pythagoreiske tripler

Et Pythagoreisk trippel er tre heltall (a, b, c) som oppfyller: $a^2+b^2=c^2$ Eksempel: (3, 4, 5) fordi $3^2+4^2=9+16=25=5^2$.

---

Pythagoreiske Tripler

Pythagoreiske tripler er tre heltall $(a,b,c)$ som oppfyller Pythagoras’ teorem:

$a^2+b^2=c^2$

Disse tallene representerer sidene i en rettvinklet trekant hvor $c$ er hypotenusen. Eksempler på slike tripler er $(3,4,5)$, $(5,12,13)$ og $(7,24,25)$.

Generering av Pythagoreiske Tripler

En metode for å finne Pythagoreiske tripler er å bruke formlene:

$a=m^2-n^2$

$b=2mn$

$c=m^2+n^2$

hvor $m$ og $n$ er to hele tall slik at $m>n>0$ og $m$ og $n$ er relativt primiske (ingen felles faktorer bortsett fra 1).

For eksempel, hvis $m=3$ og $n=2$:

$a=3^2-2^2=9-4=5$

$b=2(3)(2)=12$

$c=3^2+2^2=9+4=13$

Dermed får vi triplet $(5,12,13)$.

Primitive og Ikke-Primitive Tripler

Et Pythagoreisk trippel kalles primitivt hvis $a,b,c$ ikke har noen felles faktor større enn 1. For eksempel, $(3,4,5)$ er primitivt, mens $(6,8,10)$ ikke er det, fordi alle tallene kan deles med 2.

For å generere primitive tripler, må $m$ og $n$ være relativt primiske og ha ulik paritet (det vil si at den ene er oddetall og den andre er partall).

Anvendelser av Pythagoreiske Tripler

Pythagoreiske tripler har flere bruksområder:

• Geometri: Beregning av avstander og trekantkonfigurasjoner.
• Arkitektur: Konstruksjon av rettvinklede strukturer.
• Informatikk: Problemløsning i algoritmer, for eksempel i spillutvikling og grafikk.
• Nummerteori: Utforskning av egenskaper ved hele tall.

Liste over Noen Pythagoreiske Tripler

Her er noen små Pythagoreiske tripler:

$a$	$b$	$c$
3	4	5
5	12	13
7	24	25
8	15	17
9	40	41

Oppgaver

1. Finn ut om $(10,24,26)$ er et Pythagoreisk trippel.
2. Bruk $m=4$ og $n=1$ til å generere et nytt Pythagoreisk trippel.
3. Finn tre ikke-primitive Pythagoreiske tripler.

Referanser

• Euklid, Elementer, Bok X.
• Tallteori og geometri-leksjoner, Universitetet i Oslo.

Kapittel 5: Avanserte emner

5.1 Fermats lille teorem

Hvis p er et primtall og a er et heltall som ikke er delelig med p, da: $a^{p-1}\equiv 1(\mathrm{mod}p)$ Eksempel: $2^6\equiv 1(\mathrm{mod}7)$ fordi 7 er et primtall.

5.2 Kinesiske restteoremet

Hvis vi har kongruenser: $x\equiv a_1(\mathrm{mod}{n}_1)$ $x\equiv a_2(\mathrm{mod}{n}_2)$ med n₁ og n₂ relativt primiske, finnes en unik løsning modulo $n_1{n}_2$.

Eksempel: $x\equiv 2(\mathrm{mod}3),x\equiv 3(\mathrm{mod}5)$ Løsning: x = 8 (mod 15).