Tallteori - Sideversjonshistorikk

Administrator: /* 3.2 Lineære kongruenser */

2025-03-23T06:15:05Z

3.2 Lineære kongruenser

← Eldre sideversjon		Sideversjonen fra 23. mar. 2025 kl. 06:15
Linje 71:		Linje 71:

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

			# Addisjon: Hvis \( a \equiv b \pmod{n} \) og \( c \equiv d \pmod{n} \), så er også \( a + c \equiv b + d \pmod{n} \).
			# Multiplikasjon: Hvis \( a \equiv b \pmod{n} \), så er også \( ac \equiv bc \pmod{n} \) for alle heltall \( c \).
			# 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 ==

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

			== Se også ==
			* [[Tallteori]]
			* [[Euklids algoritme]]
			* [[RSA-kryptosystemet]]

	= Kapittel 4: Diophantiske ligninger =		= Kapittel 4: Diophantiske ligninger =

Administrator: /* 4.2 Pythagoreiske tripler */

2025-03-23T06:12:20Z

4.2 Pythagoreiske tripler

← Eldre sideversjon		Sideversjonen fra 23. mar. 2025 kl. 06:12
Linje 88:		Linje 88:

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

			{\| class="wikitable"
			! \( 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 =		= Kapittel 5: Avanserte emner =

Administrator: Ny side: ==== 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 helta…

2025-03-23T06:08:18Z

Ny side: ==== 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 helta…

Ny side

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