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: <math>\pi(n) \approx \frac{n}{\ln(n)}</math>

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: <math>84 = 2 \times 2 \times 3 \times 7</math>

---

Kapittel 3: Kongruensregning

3.1 Definisjon av kongruens

To tall a og b sies å være kongruente modulo n hvis n deler a - b: <math>a \equiv b \pmod{n}</math>

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: <math>ax \equiv b \pmod{n}</math> Løsningen finnes ved å finne inversen til a modulo n.

Eksempel: Finn x slik at <math>3x \equiv 2 \pmod{7}</math>.

Finn inversen til 3 modulo 7: <math>3^{-1} = 5</math> (fordi <math>3 \times 5 \equiv 1 \pmod{7}</math>).
Multipliser begge sider med 5:

<math>x \equiv 10 \equiv 3 \pmod{7}</math>

---

Kapittel 4: Diophantiske ligninger

4.1 Lineære Diophantiske ligninger

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

Eksempel: Finn heltallsløsninger til <math>6x + 9y = 15</math>.

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: <math>a^2 + b^2 = c^2</math> Eksempel: (3, 4, 5) fordi <math>3^2 + 4^2 = 9 + 16 = 25 = 5^2</math>.

---

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: <math>a^{p-1} \equiv 1 \pmod{p}</math> Eksempel: <math>2^6 \equiv 1 \pmod{7}</math> fordi 7 er et primtall.

5.2 Kinesiske restteoremet

Hvis vi har kongruenser: <math>x \equiv a_1 \pmod{n_1}</math> <math>x \equiv a_2 \pmod{n_2}</math> med n₁ og n₂ relativt primiske, finnes en unik løsning modulo <math>n_1 n_2</math>.

Eksempel: <math>x \equiv 2 \pmod{3}, \quad x \equiv 3 \pmod{5}</math> Løsning: x = 8 (mod 15).