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):

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

---

Primtall og Faktorisering

2.1 Primtallssetningen

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

2.2 Eratosthenes' sil

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

Skriv opp alle tall fra 2 til n.
Stryk ut alle multipler av 2 (bortsett fra 2).
Finn neste ikke-strøkede tall, stryk ut alle dets multipler.
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 (\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: $a x \equiv b (\mod n)$ Løsningen finnes ved å finne inversen til a modulo n.

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

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

$x \equiv 10 \equiv 3 (\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 (\mod n)

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

a - b = k n

Eksempel

Et eksempel på moduloregning er:

17 \equiv 5 (\mod 6)

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

Egenskaper

Moduloregning følger flere viktige regler:

**Addisjon:** Hvis $a \equiv b (\mod n)$ og $c \equiv d (\mod n)$ , så er også $a + c \equiv b + d (\mod n)$ .
**Multiplikasjon:** Hvis $a \equiv b (\mod n)$ , så er også $a c \equiv b c (\mod n)$ for alle heltall $c$ .
**Potensiering:** Hvis $a \equiv b (\mod n)$ , så er også $a^{k} \equiv b^{k} (\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

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

Se også

Kapittel 4: Diophantiske ligninger

4.1 Lineære Diophantiske ligninger

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

Eksempel: Finn heltallsløsninger til $6 x + 9 y = 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 = 2 m n

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

Finn ut om $(10, 24, 26)$ er et Pythagoreisk trippel.
Bruk $m = 4$ og $n = 1$ til å generere et nytt Pythagoreisk trippel.
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 (\mod p)$ Eksempel: $2^{6} \equiv 1 (\mod 7)$ fordi 7 er et primtall.

5.2 Kinesiske restteoremet

Hvis vi har kongruenser: $x \equiv a_{1} (\mod n_{1})$ $x \equiv a_{2} (\mod n_{2})$ med n₁ og n₂ relativt primiske, finnes en unik løsning modulo $n_{1} n_{2}$ .

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