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

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

---

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:

<math> a \equiv b \pmod{n} </math>

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

<math> a - b = kn </math>

Eksempel

Et eksempel på moduloregning er:

<math> 17 \equiv 5 \pmod{6} </math>

fordi \( 17 - 5 = 12 \), og \( 12 \) er delelig med \( 6 \).

Egenskaper

Moduloregning følger flere viktige regler:

1. **Addisjon:** Hvis \( a \equiv b \pmod{n} \) og \( c \equiv d \pmod{n} \), så er også \( a + c \equiv b + d \pmod{n} \).
2. **Multiplikasjon:** Hvis \( a \equiv b \pmod{n} \), så er også \( ac \equiv bc \pmod{n} \) for alle heltall \( c \).
3. **Potensiering:** Hvis \( a \equiv b \pmod{n} \), så er også \( a^k \equiv b^k \pmod{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 \pmod{5} \) og \( x \equiv 4 \pmod{7} \).
3. Beregn \( 2^{10} \mod 13 \).

Se også

• Tallteori
• Euklids algoritme
• RSA-kryptosystemet

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>.

---

Pythagoreiske Tripler

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

<math> a^2 + b^2 = c^2 </math>

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:

<math> a = m^2 - n^2 </math>

<math> b = 2mn </math>

<math> c = m^2 + n^2 </math>

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

<math> a = 3^2 - 2^2 = 9 - 4 = 5 </math>

<math> b = 2(3)(2) = 12 </math>

<math> c = 3^2 + 2^2 = 9 + 4 = 13 </math>

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